James R. Lee

collaborators

Showing math.MGShow all

2 papers · 1 filter

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.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…