Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations

Abstract

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)
Pages1028-1037
Number of pages10
DOIs
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

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

Cite this