The UGC Hardness Threshold of the Lp Grothendieck Problem

DOI10.1287/moor.1090.0425zbMath1216.68340OpenAlexW1999797449MaRDI QIDQ3169093

Assaf Naor, Guy Kindler, 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)

Related Items (11)

Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins ⋮ A note on the Hausdorff distance between norm balls and their linear maps ⋮ Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization ⋮ Grothendieck’s Theorem, past and present ⋮ Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems ⋮ A Greedy Algorithm for Subspace Approximation Problem ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Unnamed Item ⋮ A new semidefinite relaxation for \(L_{1}\)-constrained quadratic

This page was built for publication: The UGC Hardness Threshold of the L_p Grothendieck Problem