Matrix Spencer Conjecture

The talk is based on the paper, Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank by Nikhil Bansal, Haotian Jiang, and, Raghu Meka. arXiv link.

Abstract (from the paper)

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