15-859(J): Algorithmic Applications of Metric Embeddings

Instructors: Anupam Gupta and R. Ravi
Time: TR 1:30-2:50
Place: Wean 4615A

Course description: 

In recent years, the study of distance-preserving embeddings has given a powerful tool to algorithm designers. This course will study various aspects of embedding of metric spaces into "simpler" ones.

Topics that are likely to be covered include: embeddings of general metric spaces into normed spaces (Bourgain's theorem and its variants), improvements for planar graphs and trees, volume respecting embeddings, embeddings into trees (Bartal's theorems) and their derandomizations, improvements of these results for special metrics, low dimensional embeddings, dimensionality reduction via Johnson-Lindenstrauss lemma, generalizations to non-Euclidean norms via stable distributions. These results will be illustrated by applications to approximation algorithms (e.g., for multicommodity flow, graph bandwidth, mixtures of Gaussians), on-line algorithms (e.g., for metrical task systems), computational geometry (e.g., nearest neighbor), computation with bounded space, etc. 

Lecture Notes

  1. Sep 2. Introduction. (AG)
  2. Sep 4. Metrics in algorithms. (RR)
  3. Sep 9. Metrics in algorithms. Embeddings into linfinity. (RR)
  4. Sep 11. Bourgain's theorem: embeddings into l1 space. (Notes combined with #5.) (AG)
  5. Sep 16. Embeddings into lp spaces. Finding best Euclidean embeddings. (AG)
  6. Sep 18. Lower bounds on embeddings: flows and cuts. (AG)
  7. Sep 23. LASTs and Spanners. (RR)
  8. Sep 25. Embeddings into tree distributions. (AG)
  9. Sep 30. Embeddings into tree distributions: Random graph partitions (AG)
  10. Oct 2. Lp Embeddings from Random graph partitions (AG/RR)
  11. Oct 7. Tree Covers: Embeddings and Routing Algorithms (AG)
  12. Oct 9. Tree Metrics and Ultrametrics (RR)
  13. Oct 14. Ultrametrics and subdominance. (RR)
  14. Oct 16. Finding closest tree metrics (RR) Random Projections. (AG)
  15. Oct 21. Dimensionality Reduction and Random Projections  (AG)
  16. Oct 23. Random Projections, Lower Bounds, and embedding l2 into l1. (Notes combined with #15.) (AG)
  17. Oct 28. Approximating min-Bandwidth Layouts and Volume Respecting Embeddings. (AG)
  18. Oct 30. Volume Respecting Embeddings. (AG/RR)
  19. Nov 4. Volume Respecting Embeddings (Notes combined with #20.) (RR)
  20. Nov 6. Volume Respecting Embeddings (ends) (RR)
  21. Nov 11. Planar partitioning schemes. (RR)
  22. Nov 13. Embeddings for special graphs: Cuts and trees. (AG)
  23. Nov 18. Embeddings for series-parallel graphs. (AG)
  24. Nov 20. Lower bounds for embeddings: algebraic methods. (AG)
  25. Nov 25. Near neighbour searching. (AG)
  26. Dec 2. Max-Volume Ellipsoids, Convex Geometry and Embeddings. (AG)


  1. Homework 1, due Sept 25th.
  2. Homework 2, due October 21st.
  3. Homework 3, due Nov 11th.


Here are several books and papers covering topics related to the course. 
This is only a convenient reference list, not a syllabus of any sort. More links
will arrive later.

Last updated: 12/01/2003