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) Presentation (PDF File)

Back to Document Space