Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to conferencePaperpeer-review


We give combinatorial, geometric, and probabilistic characterizations of the distortion of tree metrics into Lp spaces. This requires the development of new embedding techniques, as well as a method for proving distortion lower bounds which is based on the wandering of Markov chains in Banach spaces, and a new metric invariant we call Markov convexity. Trees are thus the first non-trivial class of metric spaces for which one can give a simple and complete characterization of their distortion into a Hubert space, up to universal constants. Our results also yield an efficient algorithm for constructing such embeddings.

Original languageEnglish (US)
Number of pages10
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006


OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Trees and Markov convexity'. Together they form a unique fingerprint.

Cite this