Contents (hide)

Welcome to Inverse Course in Metric Embedding 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.
  • 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.

Course Schedule

Day Time Room
Tuesday 10:00-12:00room 209 building 34
Tuesday14:00-16:00room 304 building 28

Instructor

Name Web page E-mail Office Office hours
Ofer Neiman http://www.cs.bgu.ac.il/~neimano neimano at cs dot bgu dot ac dot il Building 37, Room 215 Sunday 14-16

Textbooks

  1. Jiri Matousek, Lecture notes on metric embeddings (online notes).
  2. Jiri Matousek, Lectures on Discrete Geometry (Chapter 15). McGraw-Hill 2006.
  3. 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.
Class work, 30%.