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.