Discrete Geometry of Finite Metric Spaces and Its Algorithmic Applications
- Instructor: Yoshio Okamoto
- Dates: January 11-14, 2011
- Place: Large Lecture Room, Graduate School of Information Science, Tohoku University
We discuss discrete-geometric properties of finite metric spaces.
In particular, we deal with isometric embeddability, low-distortion embeddability, and dimension reduction.
We also study algorithmic and computational aspects and their applications in large data management and network design.
Japanese (both written and spoken)
Slides and exercises
All slides and exercises are prepared in Japanese.
They will be posted here.
- Jan 11 (Tue)
- Lect 1: Introduction, and isometric embeddability
- Lect 2: Short course on optimization
- Lect 3: The sensor network localization problem
- Jan 12 (Wed)
- Lect 4: Low-distortion embedding, Johnson-Lindenstrauss Lemma
- Lect 5: Sparse solutions of a system of linear equations
- Lect 6: Nearest neighbor search
- Jan 13 (Thur)
- Lect 7: Trade-off between dimension and distortion
- Lect 8: Bourgain's embedding
- Lect 9: Lower bound via expanders
- Jan 14 (Fri)
- Lect 10: The sparsest cut problem
Online Discussion Forum and Assignment of Term-End Report (Japanese)
Visit the wiki page of the course.