Low-Dimensional Embeddings of Metric Spaces (or Can we do better than the J-L Lemma?)

lemma of Johnson and Lindenstrauss says that this metric can be embedded
into O(log n) dimensions with O(1) distortion in the distances. Moreover,
for the "uniform" metric with all n points equidistant from each other,
a simple packing argument shows that the J-L result cannot be improved.

But what if the input metric space does not have large uniform metrics?
In particular, what if the metric has low doubling dimension? It has been
conjectured that doubling Euclidean metrics can embed into O(1) dimensions
with O(1) distortion: however, nothing non-trivial was known about this
problem. (We know that linear maps like the J-L mapping cannot prove this
theorem.)

This talk will mostly consist of a survey of the concepts in this area (the
J-L lemma, doubling dimension, random partitions of metric spaces) and then
will briefly sketch some progress on these questions --- in particular, a
recent result with Hubert Chan and Kunal Talwar: one can embed any doubling
(not necessarily Euclidean) metric space into O(log log n) dimensions with
o(log n) distortion.