The UGC hardness threshold of the L_p Grothendieck problem

DOI10.1287/MOOR.1090.0425MaRDI QIDQ3169093zbMATH OpenOpenAlexFDO

Authors Guy Kindler, Assaf Naor, Gideon Schechtman

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1090.0425

zbMATH Keywords

approximation algorithmsquadratic programmingunique games hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Quadratic programming (90C20) Combinatorial optimization (90C27)

Recommendations

• The UGC hardness threshold of the l_p Grothendieck problem
• scientific article; zbMATH DE number 7053310
• Bypassing UGC from some optimal geometric inapproximability results
• Tight hardness of the non-commutative Grothendieck problem
• Quadratic forms on graphs (extended abstract)

Cited in

(17)

• The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• A new semidefinite relaxation for \(L_{1}\)-constrained quadratic
• Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization
• Grothendieck-type inequalities in combinatorial optimization
• Approximate kernel clustering
• The UGC hardness threshold of the l_p Grothendieck problem
• Tight hardness of the non-commutative Grothendieck problem
• Bypassing UGC from some optimal geometric inapproximability results
• A greedy algorithm for subspace approximation problem
• Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems
• Grothendieck’s Theorem, past and present
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• On ℓp-Gaussian–Grothendieck Problem
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• A note on the Hausdorff distance between norm balls and their linear maps
• Solving unique games over globally hypercontractive graphs

This page was built for publication: The UGC hardness threshold of the \(L_{p}\) Grothendieck problem

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