CS369: Metric Embeddings and Algorithmic Applications

Instructor: Tim Roughgarden (Gates 462)

Time/location: 11AM-12:15 PM on Mondays and Wednesdays in Gates B8.

Course description: Sample topics: low-distortion embeddings of finite metrics into L_1, L_p, and distributions of trees; dimensionality reduction; volume-respecting embeddings; applications to graph partitioning, online algorithms, network design, and nearest neighbor search. Prerequisites: CS261 or comparable mathematical maturity.

Course overview:

General references on metric embeddings:

Detailed schedule and references:

Bonus lectures (Spring 2006):