The UGC hardness threshold of the l_p Grothendieck problem

zbMATH Open1192.68910MaRDI QIDQ3579368FDOQ3579368

Authors: Guy Kindler, Assaf Naor, Gideon Schechtman 

Publication date: 6 August 2010

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

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)

Cited In (7)

• 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
• Tight hardness of the non-commutative Grothendieck problem

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)