A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP

Jeff Cheeger, Bruce Kleiner, Assaf Naor

Type: Preprint

Publication Date: 2009-10-11

Citations: 0

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+ PDF Chat	A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	Compression bounds for Lipschitz maps from the Heisenberg group to $L_1$	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+ PDF Chat	Compression bounds for Lipschitz maps from the Heisenberg group to L1	2011	Jeff Cheeger Bruce Kleiner Assaf Naor
+	Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics	2006	Hamed Hatami Avner Magen Vangelis Markakis
+	The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n	2017	Assaf Naor Robert M. Young
+	Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics	2007	Hamed Hatami Avner Magen Evangelos K. Markakis
+	Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces	2017	Yuval Rabani Rakesh Venkat
+	Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces	2017	Yuval Rabani Rakesh Venkat
+	The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of $\sqrt{\log n}$	2017	Assaf Naor Robert M. Young
+ PDF Chat	Random zero sets with local growth guarantees	2024	Alan Chang Assaf Naor K. J. Ren
+	Euclidean distortion and the Sparsest Cut	2005	Sanjeev Arora James R. Lee Assaf Naor
+ PDF Chat	Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to $\ell_1$ Embeddability of Negative Type Metrics	2008	Hamed Hatami Avner Magen Evangelos Markakis
+	Positive semidefinite relaxations for distance geometry problems	2002	Yasutoshi Yajima
+	Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain	2010	Siavosh Benabbas Avner Magen
+	L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry	2010	Assaf Naor
+	L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry	2010	Assaf Naor
+	A Geometric View of SDP Exactness in QCQPs and its Applications	2020	Alex L. Wang Fatma Kılınç-Karzan
+	Extending SDP Integrality Gaps to Sherali-Adams with Applications to	2010	Siavosh Benabbas Avner Magen
+	Tractability properties of the discrepancy in Orlicz norms	2020	Josef Dick Aicke Hinrichs Friedrich Pillichshammer Joscha Prochno

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (7)

Action	Title	Year	Authors
+ PDF Chat	Compression bounds for Lipschitz maps from the Heisenberg group to L1	2011	Jeff Cheeger Bruce Kleiner Assaf Naor
+	Manifolds with 1/4-pinched curvature are space forms	2008	Simon Brendle Richard Schoen
+	Extending Lipschitz functions via random metric partitions	2004	James R. Lee Assaf Naor
+	Euclidean distortion and the sparsest cut	2007	Sanjeev Arora James Lee Assaf Naor
+ PDF Chat	Some relations among volume, intrinsic perimeter and one-dimensional restrictions of BV functions in Carnot groups	2009	Francescopaolo Montefalcone
+ PDF Chat	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1	2005	Subhash Khot Nisheeth K. Vishnoi
+ PDF Chat	Planar Earthmover Is Not in $L_1$	2007	Assaf Naor Gideon Schechtman