{"ID":22952768,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18914","arxiv_id":"2609.18914","title":"A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer","abstract":"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.","short_abstract":"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 pol...","url_abs":"https://arxiv.org/abs/2609.18914","url_pdf":"https://arxiv.org/pdf/2609.18914v1","authors":"[\"Tarun Kathuria\"]","published":"2026-09-16T16:55:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}