Combinatorics Seminar

When: Sunday, Jan. 9, 10am
Where: Schreiber 309
Speaker: Robert Krauthgamer (IBM Almaden)
Title: Measured descent: A new embedding method for finite metrics

Abstract:

We give a new proof of Bourgain's theorem based on metric decomposition and on a technique we call "measured descent." This provides a unified framework for the two primary methods of constructing Frechet-type embeddings, those based on the work of Bourgain and of Rao. Our technique yields some interesting refinements of Bourgain's theorem in terms of important parameters of the metric space--for instance, we show that every n-point metric embeds into a Euclidean space with distortion O(sqrt{dim(X) log n}), where dim(X) is the "metric dimension" of X (which is always at most log n).

We use this technique to answer a number of open questions. For instance, our embeddings are volume-respecting for subsets of arbitrary size; this answers positively an open question of Feige. Another application achieves the optimal dimension necessary to embed planar metrics into l_infty, answering a question of Rabinovich.

This is joint work with J. R. Lee, M. Mendel, and A. Naor.