Euclidean distortion and the Sparsest Cut

Sanjeev Arora, James R. Lee, Assaf Naor

Type: Preprint

Publication Date: 2005-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.math/0508154

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Euclidean distortion and the sparsest cut	2007	Sanjeev Arora James Lee Assaf Naor
+	Inapproximability for metric embeddings into R^d	2008	Jiřı́ Matoušek Anastasios Sidiropoulos
+	Metric structures in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math>: dimension, snowflakes, and average distortion	2004	James R. Lee Manor Mendel Assaf Naor
+	Metric embedding with outliers	2015	Anastasios Sidiropoulos Yusu Wang
+ PDF Chat	Inapproximability for Metric Embeddings into R^d	2008	Jiřı́ Matoušek Anastasios Sidiropoulos
+	Terminal Embeddings	2016	Michael Elkin Arnold Filtser Ofer Neiman
+	Terminal Embeddings	2016	Michael Elkin Arnold Filtser Ofer Neiman
+	A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	Volume distortion for subsets of Euclidean spaces	2006	James R. Lee
+	Composition of nested embeddings with an application to outlier removal	2023	Shuchi Chawla Kristin Sheridan
+	Pattern Matching in Doubling Spaces	2020	Corentin Allair Antoine Vigneron
+	Pattern Matching in Doubling Spaces	2020	Corentin Allair Antoine Vigneron
+	Embedding approximately low-dimensional $\ell_2^2$ metrics into $\ell_1$	2015	Amit Deshpande Prahladh Harsha Rakesh Venkat
+	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
+ PDF Chat	Composition of nested embeddings with an application to outlier removal	2024	Shuchi Chawla Kristin Sheridan
+	A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP	2009	Jeff Cheeger Bruce Kleiner Assaf Naor
+	Entropy-based Bounds on Dimension Reduction in L_1	2011	Oded Regev
+	Entropy-based Bounds on Dimension Reduction in L_1	2011	Oded Regev
+	The Hardness of Approximation of Euclidean k-means	2015	Pranjal Awasthi Moses Charikar Ravishankar Krishnaswamy Ali Kemal Sinop

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (11)

Action	Title	Year	Authors
+	Lectures on Analysis on Metric Spaces	2001	Juha Heinonen
+ 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	On the nonexistence of uniform homeomorphisms between Lp-spaces	1970	Per Enflo
+	Small distortion and volume preserving embeddings for planar and Euclidean metrics	1999	Satish Rao
+	Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs	2005	Assaf Naor Yuval Rabani Alistair Sinclair
+ PDF Chat	The dimension of almost spherical sections of convex bodies	1977	T. Figiel Joram Lindenstrauss Vitali Milman
+	Metric structures in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:msub><mml:mrow><mml:mi>L</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math>: dimension, snowflakes, and average distortion	2004	James R. Lee Manor Mendel Assaf Naor
+	Remarks on non linear type and Pisiers inequality	2002	Assaf Naor Gideon Schechtman
+	Extending Lipschitz functions via random metric partitions	2004	James R. Lee Assaf Naor
+ PDF Chat	Embedding the diamond graph in Lp and dimension reduction in L1	2004	James R. Lee Assaf Naor