{
  "abstract": "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.15025",
  "author_total": 2,
  "authors": [
    {
      "name": "Zhao Song"
    },
    {
      "name": "Lichen Zhang"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/58dms9gsq154r.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.15025",
  "fulltext_url": null,
  "id": "58dms9gsq154r",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.15025",
  "language": null,
  "licence": "CC-BY-NC-ND-4.0",
  "licence_label": "CC BY-NC-ND 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by-nc-nd/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.FA"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "math.PR"
    ],
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W7213324262",
  "pdf_url": "https://arxiv.org/pdf/2609.15025",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-21",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/58dms9gsq154r.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:27Z",
      "native_id": "2609.15025",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.15025"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.FA",
      "subfield": "analysis-pdes"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    }
  ],
  "title": "Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input",
  "title_text": "Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input",
  "type": "preprint",
  "updated_at": "2026-10-30T12:23:27Z",
  "url": "https://research.draconitic.com/paper/58dms9gsq154r",
  "venue": "arXiv",
  "versions": []
}