Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank - Bansal, Nikhil; Jiang, Haotian; Meka, Raghu (STOC 2023, 2023)
We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric matrices each with and rank at most , one can efficiently find signs such that their signed sum has spectral norm . This result also implies a qubit lower bound for quantum random access codes encoding classical bits with advantage . 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.