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

quadratic programmingapproximation algorithmsunique games hardness

Mathematics Subject Classification ID

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

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

(16)

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

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)