The UGC hardness threshold of the L_p Grothendieck problem
DOI10.1287/MOOR.1090.0425zbMATH Open1216.68340OpenAlexW1999797449MaRDI QIDQ3169093FDOQ3169093
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
Recommendations
Quadratic programming (90C20) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (16)
- 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
- Title not available (Why is that?)
- Bypassing UGC from some optimal geometric inapproximability results
- Grothendieck-type inequalities in combinatorial optimization
- 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 Lp-Ball Constrained Homogeneous Polynomial Optimization Problems
- 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 Q3169093)
