N&O Seminar Haotian Jiang

N&O seminar on the Matrix Spencer Conjecture by Haotian Jiang

31 May 2023 from 11 a.m. to 31 May 2023 noon CEST (GMT+0200)
L017 and online

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.