Last Modified: 2007-03-23.

Notice: Most of the material in this paper library comes from two other courses:

1. Anupam Gupta and R. Ravi. At CMU.  Algorithmic Applications of Metric Embeddings.

2. Tim Roughgarden At Stanford Metric Embeddings and Algorithmic Applications


The most comprehensive survey is in Chapter 15 (latest version, 2005) of  Lectures on Discrete Geometry (Springer, May 2002) by Jiri Matousek. And the References.


  • Chapter on embeddings in Handbook of Discrete and Computational Geometry, Jiri Matousek and Piotr Indyk.
        Quick reference on many topics.
  • Survey by Piotr Indyk at FOCS 1999.
        More emphasis on algorithmic applications.
  • Finite Metric Spaces - Combinatorics, Geometry and Algorithms by Nati Linial
        Proceedings of the International Congress of Mathematicians III, 573--586 Beijing, 2002
  • Embeddings into Euclidean and l1 spaces

    Upper bounds:


    Lower bounds:


    Embeddings into distributions of trees


        Spanning trees

        Applications of random tree embeddings:


    Dimension Reduction




        Impossibility of dimensionality reduction


    Other Embeddings


        Doubling metrics and nearest neighbor search.

        Uniform sparsest cut

        Measured descent

        Volume Respecting Embeddings:

          Some Improvements:

          Inapproximability results:

        Additive Approximations to Metrics:

        Metric Property Testing:

        Growth Restrictions on Metrics:

        Metric Labeling:

        Ramsay Properties of Metrics:

        Spreading Metrics:


    Scribed Notes

    Scribe notes from a CMU course taught in Fall 2003 by Anupam Gupta and R. Ravi.