View all Seminars  |  Download ICal for this event

Matrix Discrepancy from Quantum Communication

Series: Theory Seminar

Speaker: Abhishek Shetty, PhD student,Department of Computer Science,University of California at Berkeley

Date/Time: Jan 28 11:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

In this talk, we will discuss 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 $n$ $n times n$ symmetric matrices $A_1 dots A_n$ with spectral norm bounded by 1 and Frobenius norm bounded by$n^{1/4}$, there is a signing $x$ such that $|| sum x_i A_i|| leq sqrt{n}$ We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such a sign. 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.
The talk is based on joint work with Sam Hopkins (MIT) and Prasad Raghavendra (UC Berkeley).
Microsoft Teams Link:
For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Anand Louis