Prereq.: 6.046J; 6.041 or 6.042J
Units: 3-0-9 
Time: WF 1-2:30
Location: 8-306

The concept and algorithmic applications of embeddings between metric spaces.
Embeddings of general metric spaces into normed spaces: Bourgain's lemma
and its variants, improvements for planar graphs and trees, volume respecting
embeddings. Embeddings into trees: Bartal's theorem(s),
derandomized version(s), special cases. Embeddings of normed spaces: 
dimensionality reduction via Johnson-Lindenstrauss lemma,
generalizations to non-Euclidean norms via stable distributions, 
polyhedral norms, Dudley's theorem. Hausdorff metric(s). All results
illustrated by applications to approximation algorithms
(e.g., for multicommodity flow, graph bandwidth, mixtures of Gaussians),
on-line algorithms (e.g., for metric task systems), computational geometry
(e.g., nearest neighbor, shape matching), computation with bounded space,
etc.