Haotian Jiang
University of Washington + MSR Redmond
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
This talk is centered around the Matrix Spencer Conjecture, which states that given symmetric n by n matrices A_1,...,A_n each with spectral norm at most 1, there exists +/- 1 signs x_1,... ,x_n such that their signed sum has spectral norm, or discrepancy, ||\sum_{i=1}^n x_i A_i || = O(\sqrt{n}). Randomly choosing the signs x_i will result in discrepancy O(\sqrt{n \log n}), and the conjecture says that the extraneous \sqrt{\log n} factor for random signing can be removed. This conjecture generalizes one of the most foundational results in discrepancy theory by Spencer in his famous 1985 paper "Six Standard Deviations Suffice".
In this talk, I will present a proof of this conjecture when the matrices A_i have rank at most n/\polylog(n). This resolves the Matrix Spencer Conjecture up to poly-logarithmic rank, and implies a nearly-optimal qubit lower bound for quantum random access codes encoding n classical bits with advantage >> 1/\sqrt{n}.
I will introduce the two central tools behind the proof of this result: the classical tool of partial coloring method for convex sets in [Gluskin, 1989] and [Giannopoulos, 1997] which has been widely applied in discrepancy theory, and the new tool of sharp matrix concentration inequalities 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.
