Wednesday, October 31, 2018 at 4:15pm to 5:15pm
SPEAKER: Boaz Barak (Harvard University)
TITLE: The log rank conjecture, best separable state problem, and semidefinite programming
The log rank conjecture (Lovasz and Saks, 1988) is a central conjecture in communication complexity. It is equivalent to the statement that every rank r matrix with 0/1 entries has a rank one submatrix that covers at least exp(-polylog(r)) fraction of its entries. The best known bound is by Lovett (2013) who showed that every such matrix has a rank one submatrix that covers roughly exp(-√(r)) fraction of its entries (neglecting terms that are polylogarithmic in r).
In this talk I will show a generalization of Lovett's bound to show that every rank r matrix (even without 0/1 entries) has a sub matrix that covers roughly exp(-√ (r)) fraction of its entries and is "approximately rank one" in a certain sense. We use this result to give an exp(√(n)) -time algorithm for the "Best Separable State" problem in quantum information theory, that asks, given a measurement M, to find the separable (i.e., non entangled) state that maximizes the probability that M accepts it. This is the first improvement over the brute force exp(n) algorithm for this problem.
The talk will not assume any background in quantum information theory. Based on joint work with Pravesh Kothari and David Steurer.