Embeddings of Metric Spaces and Computer Science, part I

Since we do not have an outside speaker for November 7th, I am going
to give the first of a series of occasional lectures about the
application of theorems on embeddings of metric spaces in Computer
Science.  This is a hot area of research that has inspired many exciting
developments in recent years.

I will begin by explaining the paper of Linial, London and Rabinovich
that started it all.  It related the problem of embedding an arbitrary
metric into an l_1 metric to the problem of graph partitioning.