Matrix discrepancy from Quantum communication

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 A1,…,An with ||Ai|| ≤ 1 and ||Ai||F ≤ n1/4 there exist signs x ∈ ± 1n such that the maximum eigenvalue of ∑i ≤ n xi Ai is at most O(√n). We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such x.