The UGC hardness threshold of the l_p Grothendieck problem

MaRDI QIDQ3579368zbMATH OpenFDO

Authors Guy Kindler, Assaf Naor, Gideon Schechtman

Publication date 6 August 2010

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Approximation algorithms (68W25) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

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
• Quadratic forms on graphs (extended abstract)
• Quadratic forms on graphs

Cited in

(7)

• Tight hardness of the non-commutative Grothendieck problem
• On ℓp-Gaussian–Grothendieck Problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Bypassing UGC from some optimal geometric inapproximability results
• Mathematics of computation through the lens of linear equations and lattices
• Approximate kernel clustering
• UG-hardness to NP-hardness by losing half

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