A. Naor

activity

20032005

most citedA probabilistic approach to the geometry of the \ell_p^n-ball

181 citations · 441 across the 9 of their papers we have counts for

collaborators

Showing 2005Show all

3 papers · 1 filter

cs.CG2005★ 2 cited

Planar Earthmover is not in $L_{1}$

Assaf Naor, Gideon Schechtman

We show that any $L_{1}$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid ${0, 1, ..., n}^{2} \subseteq R^{2}$ incurs distorti…

math.MG2005

Euclidean distortion and the Sparsest Cut

Sanjeev Arora, James R. Lee, Assaf Naor

We prove that every $n$ -point metric space of negative type (and, in particular, every $n$ -point subset of $L_{1}$ ) embeds into a Euclidean space with distortion $O(\sqrt{\log n} \cd…

math.PR2005★ 181 cited

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…

Planar Earthmover is not in L1​

Euclidean distortion and the Sparsest Cut

A probabilistic approach to the geometry of the \ell_p^n-ball

Planar Earthmover is not in $L_{1}$