181 citations · 1.5k across the 84 of their papers we have counts for
8 papers · 1 filter
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…
Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces
Assaf Naor, Yuval Peres, Oded Schramm +1
A metric space has {\em Markov type} 2, if for any reversible finite-state Markov chain (with chosen according to the stationary distribution) and any map f…
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…
Limitations to Frechet's Metric Embedding Method
Yair Batal, Nathan Linial, Manor Mendel +1
Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embeddi…
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…
On some low distortion metric Ramsey problems
Yair Bartal, Nathan Linial. Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces l_p. Namely, given some 1<=p<=infinity and alpha>=1, and an integer n, we ask for the largest m such that…