A Proof of the Matrix Spencer Conjecture

Abstract

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\'e inequalities to compare this partition function to that of a pinched or diagonal part of the matrix, obtaining \emph{dimension-free} constants. Our technique yields a hereditary small-ball estimate for Gaussian series that should be of independent interest. As the main application, we resolve the Matrix Spencer conjecture: for symmetric $n\times n$ matrices $A_1,\dots,A_n$ with $\|A_i\|\le1$, one can efficiently find a coloring $x\in\{\pm1\}^n$ with $\|\sum_{i=1}^n x_iA_i\|=O(\sqrt n)$.