Algorithmic Applications of Low-Distortion Embeddings
Piotr Indyk
Massachusetts Institute of Technology
Brief history of embeddings
Major results
- Impact on TCS
Dimensionality reduction: Johnson-Lindenstrauss Theorem
Theorem + construction
- Inspirations: Locally-Sensitive Hashing for Approx
Near Neighbor
- Metrics for computer vision: Earth-Mover Distance
Conclusions and Resources
Audio (MP3 File, Podcast Ready)
