Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations


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

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


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

Cite this