Please note that this newsitem has been archived, and may contain outdated information or links.
16 September 2015, Theoretical Computer Science Seminar, Jop Briet
Speaker: Jop Briet
Title: Tight Hardness of the Non-commutative Grothendieck Problem
Date: Wednesday 16 September 2015
Time: 14:00-15:00
Location: CWI room L017, Science Park 123
Abstract
We prove that for any ε>0 it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor 1/2+ε, 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.
Joint work with Oded Regev and Rishi Saket, to appear in FOCS'15.
Please note that this newsitem has been archived, and may contain outdated information or links.