CS Paper Radar

Converse symplectic interlacing via low-rank singular value perturbations

Priyanka Grover, Hemant K. Mishra, Sarishti Singh, Temjensangba

cs.IT math.FAmath-phmath.SGmath.SP ·submitted 2026-10-26 12:58 UTC · v1
theory

Abstract

The symplectic interlacing theorem states that the symplectic spectrum of a $2n \times 2n$ real symmetric positive definite matrix satisfies a $2k$-step interlacing relation with the symplectic spectrum of every $2(n-k) \times 2(n-k)$ $s$-principal submatrix. We prove the converse in this paper. More precisely, given a positive global symplectic spectrum of size $n$ and a positive local symplectic spectrum of size $n-k$ satisfying the $2k$-step interlacing inequalities, we construct a $2n \times 2n$ real symmetric positive definite matrix having the prescribed global symplectic spectrum and a $2(n-k) \times 2(n-k)$ $s$-principal submatrix of it having the prescribed local symplectic spectrum. Our main tool is a reduction of $s$-principal compression to a rank-$k$ singular value perturbation. In the context of the Gaussian quantum marginal problem, our result implies that the symplectic interlacing inequalities are not merely necessary conditions on Gaussian marginals, but are also the complete spectral compatibility conditions for the global-versus-local-mode marginal problem.

Closest papers

Nearest neighbours by meaning across the whole index.

Kadison--Singer in Deterministic Polynomial Time

cs.DS cs.DMmath.COmath.FA ·2026-09-15 ·Ekene Ezeunala, Haotian Jiang
hot direction similarity 0.55
Abstract

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

0.61

Hull Variation in Symplectic Linear Codes

cs.IT math.CO ·2026-10-11 ·Kanat Abdukhalikov, Somi Gupta, Duy Ho
theory similarity 0.54
Abstract

We study the variation of hull dimensions of symplectic linear codes under equivalence transformations preserving the symplectic distance. For a symplectic linear code $C$, we introduce an even-valued invariant $Δ(C)$, which depends only on the equivalence class of $C$. This invariant can be expressed as the generic rank of an associated space of alternating matrices and, equivalently, as twice a corresponding matroid matching number. If $C$ has dimension $k$, we prove that the minimum symplectic hull dimension among all codes equivalent to $C$ is $k-Δ(C)$. Consequently, $C$ is equivalent to a symplectic LCD code if and only if $Δ(C)=k$. We further show that every symplectic MDS code of even dimension is monomially equivalent to a symplectic LCD code. For a symplectic self-orthogonal code $C$, we determine all attainable hull dimensions: for every integer $r$ with $0\le r\le Δ(C)/2$, there exists a monomially equivalent code whose symplectic hull has dimension $k-2r$. We also refine a standard form for the generator matrix of a symplectic self-orthogonal code and derive the corresponding parity-check matrix and the Gram matrix of the dual code. In the self-dual case, we characterize $Δ(C)$ through minors of an associated symmetric matrix. Furthermore, we relate hull variation to graph matchings, establish a bound for $Δ(C)$, and give graph constructions producing symplectic self-dual MDS, optimal, and best-known codes.

0.13

Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes

cs.CC quant-phmath-ph ·2026-08-19 ·Laura Shou, Alexey V. Gorshkov, Victor Galitski, Sarah H. Miller
highly cited similarity 0.52
Abstract · 25 pages, 1 figure

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

0.50

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer

cs.DS ·2026-09-16 ·Tarun Kathuria
theory similarity 0.52
Abstract · The authors explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for …

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.49

Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the $O(N)$ Model

cs.DS math-phmath.COmath.PR ·2026-11-03 ·Jonathan Leake, Anqi Li
theory similarity 0.51
Abstract · 42 pages

Let $μ$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $λ_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.

0.28

Communication Complexity of Integer Matrix Singularity

cs.CC quant-ph ·2026-10-24 ·Chengu Wang
theory similarity 0.51
Abstract

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

0.12

Global Sinkhorn Convergence and Spectral Stability of Matrix Scaling

cs.DS ·2026-11-06 ·Kun He
theory similarity 0.51
Abstract · 71 pages

We give a global spectral bound for the Sinkhorn--Knopp (SK) algorithm. Let $A$ be a row-stochastic nonnegative $n\times n$ matrix admitting a finite doubly stochastic scaling $B$. Define \[ g=1-s_2(B)^2>0, \qquad D=\min\left\{\|(u,v)\|_\infty: B=\operatorname{diag}(e^u)A\operatorname{diag}(e^{-v})\right\}. \] From the standard initialization, SK achieves total marginal $\ell_1$ error $\varepsilon$ in \[ O\!\left(\frac{D+\log n+\log(1/\varepsilon)}{g}\right) \] iterations. A scale-invariant potential contracts globally according to the spectrum of $B$. The linear dependence on $D$ is necessary in the fixed-gap regime: we construct strictly positive inputs with constant input and endpoint spectral gaps, $D=Θ(n)$, and an $Ω(n)$ iteration lower bound at error $n^{-2}$. Our upper bound gives $O(n)$ iterations on this family. We next give spectral certificates for scalability and short scaling distance. For a row-stochastic input $A$ with positive column sums $c_j$, set \[ K=\frac{\max_jc_j}{\min_jc_j},\qquad σ=s_2\!\left(A\operatorname{diag}(c)^{-1/2}\right). \] The input-only condition $\sqrt K\,σ<1$ certifies exact scalability and polynomial scaling distortion, with $D=O(\log n)$ for fixed $K$ and a fixed positive spectral margin. Given a finite scaling $B$, the weaker condition $\sqrt K\,σs_2(B)<1$ gives the same structural bounds. With a constant endpoint gap, these bounds imply logarithmic SK iteration complexity. Boundary constructions show that the strict spectral inequalities cannot uniformly be replaced by nonstrict ones.

0.30

The Spectral Distribution of Matrix Least Squares Solutions, and the Ellipsoid Fitting Problem

cs.DS math.PRmath.STstat.ML ·2026-11-17 ·Afonso S. Bandeira, Yue M. Lu, Petar Nizić-Nikolac
similarity 0.50
Abstract · 40 pages

We study the spectral distribution of the least squares solution to a random linear system whose unknown is a symmetric matrix. In the normalized and isotropic setting, we derive a closed-form description of the support of the spectral distribution. As an application, we consider the ellipsoid fitting problem: given $n$ standard Gaussian vectors in $\mathbb{R}^d$, does there exist a centered ellipsoid passing through all of them? It was recently shown that this problem has a sharp phase transition at $n \approx d^2/4$. On the satisfiability side, unlike earlier results, these sharp results do not rely on least squares candidates. We show that the least squares candidates considered in earlier works have a threshold of positive semi-definiteness at $n \approx d^2/10$, which was previously observed numerically and predicted non-rigorously using statistical physics methods. Moreover, we show that the corresponding least squares dual certificates have a threshold of positive definiteness at $n \approx 2d^2/5$. Our approach combines several matrix concentration tools. A key technical ingredient, which may be of independent interest, is showing that a certain kernel matrix is well-conditioned with high probability until $n \approx d^2/2$.

0.39