We develop a novel connection between discrepancy minimization and (quantum)communication complexity . We resolve a substantial specialcase of the Matrix Spencer conjecture . We give a polynomial-time algorithm based on partial coloring andsemidefinite programming to find such $x . Our techniques open a new avenue to use tools from communication complexityand information theory to study discrepancy . Ourapproach also offers a promising avenue to resolve the Matrix¬†conjecture¬†completely — we show it is implied by a natural conjecture inquantum communication complexity . The proof of our main resultcombines a simple compression scheme for transcripts of repeated . (Quantum) communication protocols with quantum state purification, the Holevo bound fromquantum information, and tools from sketching and dimensionality reduction .

Author(s) : Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty

Links : PDF - Abstract

Code :

Keywords : communication - quantum - conjecture - discrepancy - matrix -

Leave a Reply

Your email address will not be published. Required fields are marked *