Tight hardness of the non-commutative Grothendieck problem

DOI10.4086/TOC.2017.V013A015zbMATH Open1387.68122arXiv1412.4413OpenAlexW2787856857MaRDI QIDQ4602402FDOQ4602402

Authors: Jop Briët, Rishi Saket, Oded Regev 

Publication date: 10 January 2018

Published in: Theory of Computing (Search for Journal in Brave)

Abstract: $ewcommandepsvarepsilon$We prove that for any $eps>0$ it is $extsfNP$-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2+eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $el{l}_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 $extsfNP$-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009).

Full work available at URL: https://arxiv.org/abs/1412.4413

Recommendations

• Efficient Rounding for the Noncommutative Grothendieck Inequality
• Efficient rounding for the noncommutative Grothendieck inequality
• Towards computing the Grothendieck constant
• The UGC hardness threshold of the \(l_p\) Grothendieck problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem

zbMATH Keywords

semidefinite programminghardness of approximationGrothendieck inequality

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Functional analysis techniques applied to functions of several complex variables (32A70)

Cited In (11)

• Moments of the Distance Between Independent Random Vectors
• Complexity and algorithms for finding a subset of vectors with the longest sum
• Failure of the trilinear operator space Grothendieck theorem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Approximability of the problem of finding a vector subset with the longest sum
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Survey on nonlocal games and operator space theory
• Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness
• On sketching the \(q\) to \(p\) norms
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms

This page was built for publication: Tight hardness of the non-commutative Grothendieck problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4602402)