Trees and Markov convexity

James R. Lee; Assaf Naor; Yuval Peres

doi:10.1145/1109557.1109671

Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Mathematics

Research output: Contribution to conference › Paper › peer-review

Abstract

We give combinatorial, geometric, and probabilistic characterizations of the distortion of tree metrics into L_p 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 language	English (US)
Pages	1028-1037
Number of pages	10
DOIs	https://doi.org/10.1145/1109557.1109671
State	Published - 2006
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Other

Other	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	1/22/06 → 1/24/06

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

10.1145/1109557.1109671

Cite this

@conference{a82c39020dcc4ec3ac81e351560b961b,

title = "Trees and Markov convexity",

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.",

author = "Lee, {James R.} and Assaf Naor and Yuval Peres",

year = "2006",

doi = "10.1145/1109557.1109671",

language = "English (US)",

pages = "1028--1037",

note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

TY - CONF

T1 - Trees and Markov convexity

AU - Lee, James R.

AU - Naor, Assaf

AU - Peres, Yuval

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33244484172&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244484172&partnerID=8YFLogxK

U2 - 10.1145/1109557.1109671

DO - 10.1145/1109557.1109671

M3 - Paper

AN - SCOPUS:33244484172

SP - 1028

EP - 1037

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

Trees and Markov convexity

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this