MIT Electrical Engineering and Computer Science Fall 2000 Catalogue Supplement

6.978 Algorithmic Aspects of Embeddings (H)

MW 1-2:30, Room 8-306
Professor Piotr Indyk
Prereq.: 6.046J, 6.041 or 6.042J
3-0-9

Does not count as an Engineering Concentration Subject.

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 verson(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.