Contents (hide)

Welcome to Metric Embedding and its Algorithmic Applications homepage

Course Description

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.

Course Schedule

Day Time Room
Sunday 10:00-12:00Building 90, Room 237
Monday10:00-12:00Building 90, Room 237


Name Web page E-mail Office Office hours
Ofer Neiman neimano at cs dot bgu dot ac dot il Building 37, Room 215 Sunday 12-14


  1. Jiri Matousek, Lectures on Discrete Geometry (Chapter 15). McGraw-Hill 2006.
  2. Michel Deza. Monique Laurent, Geometry of Cuts and. Metrics (link). Springer 1997.

Grading Policy

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.