TITLE:  Trees and Markov convexity

ABSTRACT:

Consider the following question:  Given a tree metric T (i.e. the 
shortest-path metric on some edge-weighted tree), when does T embed into a 
Hilbert space with bounded distortion?  We give probabilistic, geometric, 
and combinatorial characterizations which involve, for instance, the 
relationship between the convexity of a geometric space and the wandering 
of Markov chains which take values in that space.  This allows us to 
answer computational problems like:  Given an n-point tree T, and some 
value p, find a near-optimal embedding of T into R^n under the L_p 
norm.

Joint work with Assaf Naor and Yuval Peres.