{"id":"arxiv/2609.15025","url":"https://arxiv.org/abs/2609.15025","tags":["cs.DS","math.FA","math.OC","math.PR"],"score":0,"title":"Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input","domain":"cs.DS","source":"arxiv","authors":["Zhao Song","Lichen Zhang"],"reviews":0,"subject":"cs.DS","summary":"The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\\ldots,A_n\\in\\mathbb{R}^{n\\times n}$ with $\\|A_i\\|\\le1$ there are signs $\\varepsilon_1,\\ldots,\\varepsilon_n\\in\\{-1,1\\}$ with $\\|\\sum_{i=1}^n\\varepsilon_iA_i\\|=O(\\sqrt n)$. We prove it: a signing of discrepancy below $8\\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\\operatorname{polylog}(1/p)$ arithmetic operations in the real-arithmetic model. This matches the size $n^3$ of the dense…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}