# 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
- 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.

[Teaching Top]

okamotoy@uec.ac.jp