Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to conferencePaper

8 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 - Jan 1 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
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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

  • Cite this

    Lee, J. R., Naor, A., & Peres, Y. (2006). Trees and Markov convexity. 1028-1037. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109671