scientific article

DOI10.4086/toc.2009.v005a004zbMath1213.68313OpenAlexW1591762700MaRDI QIDQ3002802

Subhash A. Khot, Ryan O'Donnell

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2009.v005a004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

quadratic programmingsemidefinite programmingFourier analysismax-cutunique games conjectureGrothendieck inequalityGaussian spacedictator testingmax-cut-gainsemidefinite programming gaps

Mathematics Subject Classification ID

Semidefinite programming (90C22) Quadratic programming (90C20) Inequalities and extremum problems involving convexity in convex geometry (52A40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms, Grothendieck-Type Inequalities in Combinatorial Optimization, Pseudorandom sets in Grassmann graph have near-perfect expansion, Approximating sparse quadratic programs, Mathematics of computation through the lens of linear equations and lattices, \textsc{Max-Cut} parameterized above the Edwards-Erdős bound, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁