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 A 1 ,…, A n with || A i || ≤ 1 and || A i || F ≤ n 1/4 there exist signs x ∈ { ± 1} n 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 .

Authors

• Samuel B. Hopkins 0001
• Prasad Raghavendra
• Abhishek Shetty

Keywords

• Matrix Discrepancy
• Quantum Communication Complexity
• Quantum Random Access Codes
• Semidefinite Programming
• Sketching