Tight hardness of the non-commutative Grothendieck problem

Computer Science/Discrete Mathematics Seminar I
Topic:Tight hardness of the non-commutative Grothendieck problem
Speaker:Oded Regev
Affiliation:New York University
Date:Monday, March 16
Time/Room:11:15am - 12:15pm/S-101
Video Link:http://video.ias.edu/csdm/2015/0316-OdedRegev

We prove that for any $\epsilon > 0$ it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \epsilon$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $\ell_2$ into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates. The talk does not assume familiarity with the Grothendieck problem. Joint work with Jop Briet and Rishi Saket.