72 citations · 126 across the 3 of their papers we have counts for
3 papers
math.MG2005
Euclidean distortion and the Sparsest Cut
Sanjeev Arora, James R. Lee, Assaf Naor
We prove that every -point metric space of negative type (and, in particular, every -point subset of ) embeds into a Euclidean space with distortion $O(\sqrt{\log n} \cd…
cs.DS2004★ 72 cited
Measured descent: A new embedding method for finite metrics
Robert Krauthgamer, James R. Lee, Manor Mendel +1
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability me…
math.MG2004★ 54 cited
Metric structures in L_1: Dimension, snowflakes, and average distortion
James R. Lee, Manor Mendel, Assaf Naor
We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weight…