Abstract
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 × n matrices A₁,…,A_n with A_i ≤ 1 and A_i_F ≤ n^1/4 there exist signs x ∈ { ± 1}ⁿ such that the maximum eigenvalue of Σ_i ≤ n x_i A_i is at most O(√n). We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such x. Our techniques open a new avenue to use tools from communication complexity and information theory to study discrepancy. The proof of our main result combines a simple compression scheme for transcripts of repeated (quantum) communication protocols with quantum state purification, the Holevo bound from quantum information, and tools from sketching and dimensionality reduction. Our approach also offers a promising avenue to resolve the Matrix Spencer conjecture completely -- we show it is implied by a natural conjecture in quantum communication complexity.