Matrix Discrepancy from Quantum Communication

Understand

We develop a novel connection between discrepancy minimization and (quantum) communication complexity.

• As an application, we resolve a substantial special case of the Matrix Spencer conjecture.
• In particular, we show that for every collection of symmetric $n \times n$ matrices $A_1,\ldots,A_n$ with $\|A_i\| \leq 1$ and $\|A_i\|_F \leq n^{1/4}$ there exist signs $x \in \{ \pm 1\}^n$ such that the maximum eigenvalue of $\sum_{i \leq n} x_i A_i$ is at most $O(\sqrt n)$.
• We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such $x$.