SDP Integrality Gaps with Local ell_1-Embeddability

DOI10.1109/FOCS.2009.37zbMath1292.90228OpenAlexW2166536886MaRDI QIDQ5171220

Rishi Saket, Subhash A. Khot

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

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

Related Items

Sketching and Embedding are Equivalent for Norms, Making the Long Code Shorter, Unnamed Item, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Unnamed Item, Convex Relaxations and Integrality Gaps, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Unnamed Item, Unnamed Item, Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem, An Improved Dictatorship Test with Perfect Completeness