Publication
FOCS 2015
Conference paper

Tight Hardness of the Non-commutative Grothendieck Problem

View publication

Abstract

We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of finite-dimensional Hilbert spaces 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.

Date

Publication

FOCS 2015

Authors

Share