#### Theory Seminar

# Haotian Jiang: Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank

Haotian JiangUniversity of Washington

WHERE:

3725 Beyster BuildingMap

WHEN:

Friday, October 14, 2022 @ 3:00 pm - 4:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

WEB: Event Website

SHARE:

(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.