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


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.