Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric \(d \times d\) matrices \(A_1,\ldots,A_n\) each with \(\|A_i\|_{\mathsf{op}} \leq 1\) and rank at most \(n/\log^3 n\), one can efficiently find \(\pm 1\) signs \(x_1,\ldots,x_n\) such that their signed sum has spectral norm \(\|\sum_{i=1}^n x_i A_i\|_{\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, 2021] for random matrices with correlated Gaussian entries.