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.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

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 -