Georgia Institute of Technology College of Sciences

In this talk, I will present a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d by d matrices A_1,...,A_n each with operator norm at most 1 and rank at most n/\log^3 n, one can efficiently find \pm 1 signs x_1,... ,x_n such that their signed sum has spectral norm \|\sum_{i=1}^n x_i A_i\|_op= O(\sqrt{n}). This result also implies a (\log n - 3 \log \log n) qubit lower bound for quantum random access codes encoding n classical bits with advantage >> 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.