OP-00061 Solution claimed

The Matrix Spencer conjecture

Let $\|\cdot\|$ be the spectral norm. For commuting matrices the question reduces to Spencer's "six standard deviations suffice" theorem, and the non-commutative Khintchine inequality gives the bound below up to a factor $\sqrt{\log n}$. Bansal, Jiang and Meka proved it for matrices of rank up to $n$ divided by a polylogarithmic factor.

Problem. Prove or disprove that there is a positive universal constant $C$ such that, for all positive integers $n$ and all self-adjoint $A_1, \dots, A_n \in \mathbb{R}^{n \times n}$ with $\|A_i\| \le 1$, $$\min_{\varepsilon \in \{\pm1\}^n} \Bigl\|\sum_{i=1}^n \varepsilon_i A_i\Bigr\| \le C\sqrt n.$$

Source: First posed by Zouzias (ICALP 2012), according to Bandeira, and discussed in Meka's 2014 blog post. Conjecture 1 of Randomstrasse101, in Bandeira's “Welcome, and Matrix Discrepancy” (2024); Entry 1 of arXiv:2504.20539.

The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.

Classification

Primary: CO — Combinatorics
Secondary: FA, PR
Keywords: discrepancy theory, Matrix Spencer, random matrices, Randomstrasse101
Literature checked: Oct. 2, 2026 by clemens-admin

References

@misc{randomstrasse2024,
  author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
  title = {{Randomstrasse101}: Open Problems of 2024},
  year = {2025},
  eprint = {2504.20539},
  archivePrefix = {arXiv}
}

@inproceedings{zouzias2012,
  author = {Zouzias, Anastasios},
  title = {A matrix hyperbolic cosine algorithm and applications},
  booktitle = {Automata, Languages, and Programming (ICALP 2012)},
  year = {2012}
}

@misc{meka2014,
  author = {Meka, Raghu},
  title = {Discrepancy and beating the union bound},
  howpublished = {Windows On Theory (blog)},
  year = {2014},
  url = {https://windowsontheory.org/2014/02/07/discrepancy-and-beating-the-union-bound}
}

@article{spencer1985,
  author = {Spencer, Joel},
  title = {Six standard deviations suffice},
  journal = {Transactions of the American Mathematical Society},
  volume = {289},
  number = {2},
  pages = {679--706},
  year = {1985}
}

@inproceedings{bansal2023matrixspencer,
  author = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu},
  title = {Resolving {M}atrix {S}pencer conjecture up to poly-logarithmic rank},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
  year = {2023}
}

Resolution claims

A Proof of the Matrix Spencer Conjecture v1 arXiv ↗ AI-Verified

Emrullah Akbas; Suvrit Sra

We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We then employ matrix-weighted Poincaré inequalities to compare this partition function to that of a pinched or diagonal part of the …

Full resolution · not verified · fidelity not established · posted on arXiv 28 Aug 2026

Status history

When	Change	By	Reason
2026-10-04	Open → Solution claimed	The registry's curators	A Proof of the Matrix Spencer Conjecture v1 recorded from arXiv:2608.28816v1.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00061, "The Matrix Spencer conjecture", clopen.solutions.