Welcome to Inverse Course in Metric Embedding homepage
The analysis of metrics plays an important role in various disciplines of computer science. This course deals with the theory of metric embeddings and it reviews standard, widely applicable techniques like dimension reduction, random partitions and sampling.
Some of the possible topics are:
- Dimension reduction and random projections.
- Embedding into Euclidean space.
- Embedding graphs into trees via random decompositions.
- Lower bounds on embeddings.
- Cuts and flows via embeddings.
- Spanners and distance oracles.
The course will be given as an "inverse course", where we will do assignments at class, and read lecture notes at home.
|Tuesday ||10:00-12:00||room 209 building 34
|Tuesday||14:00-16:00||room 304 building 28
Jiri Matousek, Lecture notes on metric embeddings (online notes).
Jiri Matousek, Lectures on Discrete Geometry (Chapter 15). McGraw-Hill 2006.
Michel Deza. Monique Laurent, Geometry of Cuts and. Metrics (link). Springer 1997.
Final exam, 70%. Students MUST PASS the exam to pass the course.
Class work, 30%.