Theory of Computing
-------------------
Title : Tight Hardness of the Non-Commutative Grothendieck Problem
Authors : Jop Briet, Oded Regev, and Rishi Saket
Volume : 13
Number : 15
Pages : 1-24
URL : https://theoryofcomputing.org/articles/v013a015
Abstract
--------
We prove that for any $\eps > 0$ it is NP-hard to approximate the non-
commutative Grothendieck problem to within a factor $1/2 + \eps$,
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. We also observe that one can obtain
a tight NP-hardness result for the _commutative_ Little Grothendieck
problem; previously, this was only known based on the Unique Games
Conjecture (Khot and Naor, Mathematika 2009).
A conference version of this paper appeared in the Proceedings of
the 56th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2015).