CS Paper Radar

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

Tarun Kathuria

cs.DS ·submitted 2026-09-18 03:45 UTC · v2
theory

Abstract

Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_i A_i=I$ and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each original matrix with discrepancy $O(\sqrt{\varepsilon\log(2r)})$, independently of their dimension and number, which is known to be optimal upto constants. We give a separate existence proof and a deterministic algorithm with polynomial work in a real-arithmetic model with semidefinite-value and exact spectral primitives. Separate Lean formalizations verify the existence proof and the algorithm in this arithmetic model. The proof extends the variational approach to discrepancy developed in the companion papers, motivated by operator-valued free interpolation, Lehner's formula, and spectral Tsallis regularization. A concave matrix power interpolates between a trace source and a sandwich source. Its concavity controls the response of the optimizing density. The walk maintains independent source reserves and a second matrix recording reserve expenditure. This matrix certifies contraction of the unfinished input mass between epochs; within an epoch, preparation and a negative-curvature step control the spectral potential while the coefficients advance toward signs. As applications, one spanning tree can be chosen simultaneously $O(\varepsilon\log(2s))$-spectrally thin for $s$ positive weightings of a common graph whose edge leverages are at most $\varepsilon$. The diagonal specialization gives discrepancy $O(\sqrt{L\log(2k)})$ for matrices with row sums at most $L$ and at most $k$ nonzero entries per column, through a walk of fractional colorings.

Comment
The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for the purpose of training artificial intelligence systems or for text and data mining (TDM), including but not limited to the generation of embeddings, summaries, or synthetic derivatives

Closest papers

Nearest neighbours by meaning across the whole index.

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

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

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.56

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

cs.DS ·2026-09-16 ·Tarun Kathuria
theory similarity 0.70
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

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

cs.DS math.COmath.FAmath.OC ·2026-09-20 ·Ali Jadbabaie, Amin Saberi, Suvrit Sra
theory similarity 0.69
Abstract · Sharing early for feedback. Exposition is being improved for the next revision. Github for certificates will be made available in the near f…

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison--Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $Δ\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(Δ-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{Δ-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.

0.45

Polynomial Time Algorithms for the Kadison-Singer Problem

cs.DS ·2026-09-17 ·Zhao Song, Song Yue
hot direction similarity 0.65
Abstract

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $σ\in\{\pm1\}^m$ satisfying $\|\sum_i σ_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{4.75})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{3.58})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\leα$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrtα$ for $j=1,2$.

0.45

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.64
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45

UPP$^{\text{cc}}$ is Not Closed Under Intersection

cs.CC ·2026-10-27 ·Mark Bun, Mandar Juvekar
theory similarity 0.63
Abstract

The sign rank of a ${\pm 1}$-valued matrix $A$ is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. For every sufficiently large $d$, we give an explicit matrix $A$ with $2^{Θ(d^2)}$ rows and columns and sign rank $Θ(d)$ such that $A \land A$ has sign rank $2^{Θ(d)}$. Here, $A \land A$ is the communication matrix of the problem obtained by evaluating $A$ on disjoint inputs and taking the conjunction of the results. As the logarithm of sign rank characterizes unbounded-error communication complexity, this implies that the communication class $\mathsf{UPP}^{\mathsf{cc}}$ is not closed under intersection. The starting point for our lower bound is Forster's method, which relates the sign rank of a matrix to the average margin of representations of its rows and columns by points and halfspaces. We study a continuous analog for conjunctions of inner-product sign tests on the unit sphere. Rotational symmetry connects this problem to polynomial sign representations, yielding an exponentially small upper bound on the average margin. This bound holds even when sign constraints are relaxed near the sign tests' decision boundary, allowing us to transfer it to explicit finite sign matrices arising from intersections of integer halfspaces.

0.22

Stable and Online Algorithms for Random Matrix Discrepancy

cs.DS cs.CCcs.DMmath.CO+1 ·2026-10-01 ·Eren C. Kızıldağ, Shuangping Li
theoryhighly cited similarity 0.63
Abstract

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\dots,σ_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N σ_i A_i$ is at most $κ\sqrt{N}$. Focusing on the proportional regime $N/d^2\to τ\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $κ\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \emph{recenter-and-round} algorithm that is noise-stable and succeeds whenever $τ=Ω(\frac{1}{κ^2\log(1/κ)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the \emph{Frobenius-greedy} algorithm, establishing that it succeeds when $τ>τ_{\rm FG}(κ)\sim \fracπ{4κ^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $Θ(\frac{1}{κ^2\log(1/κ)})$ for stable offline algorithms and $Θ(\frac{1}{κ^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $Θ(\log(1/κ))$, as shown by Maillard~\cite{maillard2025}.

0.30

The Komlós Problem in Matrix-Multiplication Time

cs.DS cs.DM ·2026-10-14 ·Emile Anand, Peter Chen
similarity 0.62
Abstract · 30 pages

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

0.39