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.
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.
Upper bounds:
Lower bounds:
Applications of random tree embeddings:
Volume Respecting Embeddings:
Additive Approximations to Metrics:
Metric Property Testing:
Growth Restrictions on Metrics:
Metric Labeling:
Ramsay Properties of Metrics:
Last updated: 12/01/2003