Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to conferencePaper

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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this