Discrete Geometry of Finite Metric Spaces and Its Algorithmic Applications

Fall 2010

Administrivia

Instructor: Yoshio Okamoto
Dates: January 11-14, 2011
Place: Large Lecture Room, Graduate School of Information Science, Tohoku University

Topic

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.

Language

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
  - Slides (Jan 14, revised)
  - Slides (4up) (Jan 14, revised)
  - Exercises (Jan 11, revised)
- Lect 2: Short course on optimization
  - Slides (Jan 11, revised)
  - Slides (4up) (Jan 11, revised)
  - Exercises
- Lect 3: The sensor network localization problem
  - Slides
  - Slides (4up)
Jan 12 (Wed)
- Lect 4: Low-distortion embedding, Johnson-Lindenstrauss Lemma
  - Slides (Jan 13, revised)
  - Slides (4up) (Jan 13, revised)
  - Exercises
- Lect 5: Sparse solutions of a system of linear equations
  - Slides (Jan 13, revised)
  - Slides (4up) (Jan 13, revised)
  - Exercises (Jan 13, revised)
- Lect 6: Nearest neighbor search
Jan 13 (Thur)
- Lect 7: Trade-off between dimension and distortion
  - Slides (revised Jan 14)
  - Slides (4up) (revised Jan 14)
  - Exercises
- Lect 8: Bourgain's embedding
- Lect 9: Lower bound via expanders
Jan 14 (Fri)
- Lect 10: The sparsest cut problem
  - Slides (revised Jan 14)
  - Slides (4up) (revised Jan 14)

Online Discussion Forum and Assignment of Term-End Report (Japanese)

Visit the wiki page of the course.

[Teaching Top]

okamotoy@uec.ac.jp