### DIMACS Theoretical Computer Science Seminar

Title: Trees and Markov convexity

Speaker: **James R. Lee**, Institute for Advanced Study

Date: November 15, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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.