Metraipolis › archive › dc_8510df2bdfc0
Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input — arXiv:2609.15025
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15025
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T00:39:33.399Z
- SHA-256 of the archived text
c7fcc949d5135400a95c73487b1cee54f0e9f4aa96928571f56d32006a929ce6- Stable URL of this page
https://metraipolis.com/documento/dc_8510df2bdfc0
How to cite
Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input — arXiv:2609.15025 — arXiv (en), https://arxiv.org/abs/2609.15025 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8510df2bdfc0 (Metraipolis archive dc_8510df2bdfc0, sha256 c7fcc949d5135400a95c73487b1cee54f0e9f4aa96928571f56d32006a929ce6)
BibTeX
@misc{dc8510df2bdfc0,
title = {Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input — arXiv:2609.15025},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15025},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8510df2bdfc0; sha256 c7fcc949d5135400a95c73487b1cee54f0e9f4aa96928571f56d32006a929ce6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15025. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 input up to subpolynomial factors. In the other direction, we prove that for every $n$ there are collections of symmetric matrices such that every signing has discrepancy at least $(2-o(1))\sqrt{n}$. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body $\{x\in \mathbb{R}^n:\|\sum_ix_iA_i\|\le R\}$ that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant $7\cdot10^9$. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The $n^{3+o(1)}$ time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.OC).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Functional Analysis (math.FA); Optimization and Control (math.OC); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.15025 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T00:16:48.875Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).