TY - GEN
T1 - Tight Hardness of the Non-commutative Grothendieck Problem
AU - Briot, Jop
AU - Regev, Oded
AU - Saket, Rishi
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - 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.
AB - 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.
KW - Grothendieck inequality
KW - hardness
KW - semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=84960423518&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960423518&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.72
DO - 10.1109/FOCS.2015.72
M3 - Conference contribution
AN - SCOPUS:84960423518
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1108
EP - 1122
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -