181 citations · 441 across the 9 of their papers we have counts for
9 papers
Planar Earthmover is not in
Assaf Naor, Gideon Schechtman
We show that any embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid incurs distorti…
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…
A probabilistic approach to the geometry of the \ell_p^n-ball
Franck Barthe, Olivier Guedon, Shahar Mendelson +1
This article investigates, by probabilistic methods, various geometric questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms of independent random variabl…
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…
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…
On Metric Ramsey-type Dichotomies
Yair Bartal, Nathan Linial, Manor Mendel +1
The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of…