### Abstract

We prove that for any e > 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. 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).

Original language | English (US) |
---|---|

Journal | Theory of Computing |

Volume | 13 |

DOIs | |

State | Published - Dec 2 2017 |

### Keywords

- Grothendieck inequality
- Hardness of approximation
- Semidefinite programming

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Tight hardness of the non-commutative grothendieck problem'. Together they form a unique fingerprint.

## Cite this

Briët, J., Regev, O., & Saket, R. (2017). Tight hardness of the non-commutative grothendieck problem.

*Theory of Computing*,*13*. https://doi.org/10.4086/toc.2017.v013a015