Welcome to Metric Embedding and its Algorithmic Applications 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.
|Sunday ||10:00-12:00||Building 90, Room 237
|Monday||10:00-12:00||Building 90, Room 237
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.
Homework assignments, 30%. There will be 3 homework assignments.
You may hand in the exercises either by yourself or with one other student.
Students whose partner has a valid reason not to hand in some assignment must
still hand in the assignment. You may not hand in the assignments in groups
larger than two. Cheating will not be tolerated.