2015-10-18
Tight hardness of the non-commutative Grothendieck problem
Publication
Publication
Presented at the
Annual IEEE Symposium on Foundations of Computer Science (October 2015)
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 ℓ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.
| Additional Metadata | |
|---|---|
| IBM Research, Bangalore, India | |
| doi.org/10.1109/FOCS.2015.72 | |
| Annual IEEE Symposium on Foundations of Computer Science | |
| Organisation | Algorithms and Complexity |
|
Briët, J., Regev, O., & Saket, R. (2015). Tight hardness of the non-commutative Grothendieck problem. doi:10.1109/FOCS.2015.72 |
|
| See Also |
|---|
