Tight hardness of the non-commutative Grothendieck problem

DOI10.4086/TOC.2017.V013A015MaRDI QIDQ4602402zbMATH OpenOpenAlexFDO

Authors Jop Briët, Rishi Saket, Oded Regev

Publication date 10 January 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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).

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

Cited in

(11)

• Moments of the Distance Between Independent Random Vectors
• Complexity and algorithms for finding a subset of vectors with the longest sum
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Failure of the trilinear operator space Grothendieck theorem
• 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
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• On sketching the \(q\) to \(p\) norms
• 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)