Briët, Jop; Regev, Oded; Saket, Rishi Tight hardness of the non-commutative Grothendieck problem. (English) Zbl 1387.68122 Theory Comput. 13, Paper No. 15, 24 p. (2017). Summary: We prove that for any \(\varepsilon > 0\) it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor \(1/2 + \varepsilon\), which matches the approximation ratio of the algorithm of A. Naor et al. [Theory Comput. 10, Paper No. 11, 257–295 (2014; Zbl 1302.68323)]. Our proof uses an embedding of \(\ell_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 [S. Khot and A. Naor, Mathematika 55, No. 1–2, 129–165 (2009; Zbl 1195.68114)]. Cited in 1 ReviewCited in 7 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory 32A70 Functional analysis techniques applied to functions of several complex variables 68W25 Approximation algorithms 90C22 Semidefinite programming Keywords:hardness of approximation; semidefinite programming; Grothendieck inequality Citations:Zbl 1302.68323; Zbl 1195.68114 PDFBibTeX XMLCite \textit{J. Briët} et al., Theory Comput. 13, Paper No. 15, 24 p. (2017; Zbl 1387.68122) Full Text: DOI arXiv