SDP Integrality Gaps with Local ell₁-Embeddability

DOI10.1109/FOCS.2009.37MaRDI QIDQ5171220zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Rishi Saket

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.37

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Semidefinite programming (90C22)

Cited in

(14)

• Convex relaxations and integrality gaps
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Making the Long Code Shorter
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Sketching and embedding are equivalent for norms
• Superlinear Integrality Gaps for the Minimum Majority Problem
• An improved dictatorship test with perfect completeness
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Majority is stablest: discrete and SoS
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)

This page was built for publication: SDP Integrality Gaps with Local ell_1-Embeddability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171220)