@inproceedings{bansal2023resolving,
author = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu},
title = {Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank},
organization = {ACM},
booktitle = {STOC 2023},
year = {2023},
month = {June},
abstract = {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 - \Omesdfsdf \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.},
url = {http://approjects.co.za/?big=en-us/research/publication/resolving-matrix-spencer-conjecture-up-to-poly-logarithmic-rank/},
}