The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

Similar Works

Action	Title	Year	Authors
+	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	A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+ PDF Chat	On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension	2020	Fernando Mário de Oliveira Filho Frank Vallentin
+	Merging techniques for combinatorial optimization: spectral graph theory and semidefinite programming	2009	Umesh Vazirani Alexandra Kolla
+	Merging Techniques for Combinatorial Optimization: Spectral Graph Theory and Semidefinite Programming - eScholarship	2009	Alexandra Kolla
+ PDF Chat	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems	2014	Venkatesan Guruswami Ali Kemal Sinop Yuan Zhou
+	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems	2012	Venkatesan Guruswami Ali Kemal Sinop Yuan Zhou
+	Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs	2021	Andrés López-Martínez Sagnik Mukhopadhyay Danupon Nanongkai
+	Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs	2021	Andrés López-Martínez Sagnik Mukhopadhyay Danupon Nanongkai
+	Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs	2021	Zhiyang He Jason Li Magnus Wahlström
+	Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth	2023	Richard Y. Zhang
+	Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs	2020	Zhiyang He Jason Li Magnus Wahlström
+	Cutting planes for semidefinite relaxations based on triangle-free subgraphs	2015	Abraham Berman Mirjam Dür Naomi Shaked-Monderer Julia Witzel
+	Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy	2011	Siavosh Benabbas Siu On Chan Konstantinos Georgiou Avner Magen
+	Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming	2018	Charles Carlson Alexandra Kolla Ray Li Nitya Mani Benny Sudakov Luca Trevisan
+	Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming	2018	C. W. Carlson Alexandra Kolla Ray Li Nitya Mani Benny Sudakov Luca Trevisan
+	Strong SDP based bounds on the cutwidth of a graph	2023	Elisabeth Gaar Diane Puges Angelika Wiegele
+	Integrality gaps for strong linear programming and semidefinite programming relaxations	2010	Konstantinos Georgiou

Works That Cite This (8)

Action	Title	Year	Authors
+ PDF Chat	Foliated corona decompositions	2022	Assaf Naor Robert M. Young
+	Negative type diversities, a multi-dimensional analogue of negative type metrics	2018	Pei Wu David Bryant Paul Tupper
+	Vertical perimeter versus horizontal perimeter	2017	Assaf Naor Robert M. Young
+	Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group	2018	Katrin Fässler Tuomas Orponen Séverine Rigot
+ PDF Chat	Vertical perimeter versus horizontal perimeter	2018	Assaf Naor Robert M. Young
+	Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group	2020	Katrin Fässler Tuomas Orponen Séverine Rigot
+ PDF Chat	Negative-Type Diversities, a Multi-dimensional Analogue of Negative-Type Metrics	2019	Pei Wu David Bryant Paul Tupper
+	Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces	2017	Yuval Rabani Rakesh Venkat

Works Cited by This (63)

Action	Title	Year	Authors
+	Plongements lipschitziens dans Rn	2003	Patrice Assouad
+	Geometric Nonlinear Functional Analysis	1999	Yoav Benyamini Joram Lindenstrauss
+	A Course in Metric Geometry	2001	Dmitri Burago Yuri Burago S. V. Ivanov
+ PDF Chat	A T(b) theorem with remarks on analytic capacity and the Cauchy integral	1990	Michael Christ
+	The Degree of Polynomial Growth of Finitely Generated Nilpotent Groups	1972	Hyman Bass
+	On the structure of finite perimeter sets in step 2 Carnot groups	2003	Bruno Franchi Raul Serapioni Francesco Serra Cassano
+ PDF Chat	Compression bounds for Lipschitz maps from the Heisenberg group to L1	2011	Jeff Cheeger Bruce Kleiner Assaf Naor
+ PDF Chat	Trees and Markov Convexity	2008	James R. Lee Assaf Naor Yuval Peres
+	Small distortion and volume preserving embeddings for planar and Euclidean metrics	1999	Satish Rao
+	On the distribution of the fourier spectrum of Boolean functions	2002	Jean Bourgain