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)
Back to Document Space