Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

Abstract

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric $d\times d$ matrices $A_1,\dots ,A_n$ each with $\Vert A_i{\Vert }_{\mathsf{op}}\le 1$ and rank at most $n/{\log }^{3}n$, one can efficiently find $\pm 1$ signs $x_1,\dots ,x_n$ such that their signed sum has spectral norm $\Vert {\sum }_{i=1}^n{x}_i{A}_i{\Vert }_{\mathsf{op}}=O(\sqrt{n})$. This result also implies a $\log n-\Omega (\log \log n)$ qubit lower bound for quantum random access codes encoding $n$ classical bits with advantage $\gg 1/\sqrt{n}$. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries.