Haotian Jiang: Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank

(Zoom password: 728726)

Abstract: 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. This talk is based on a joint work with Nikhil Bansal and Raghu Meka, available at https://arxiv.org/abs/2208.11286.