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 d × d matrices A_1,…,A_n each with \|A_i\|_[[op]] ≤ 1 and rank at most n/^3 n, one can efficiently find ± 1 signs x_1,…,x_n such that their signed sum has spectral norm \|_[i=1]^n x_i A_i\|_[[op]] = O([n]). This result also implies a n - Ω( n) qubit lower bound for quantum random access codes encoding n classical bits with advantage 1/[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.