18.409 Topics in Theoretical Computer Science

When and where: The class meets on Mondays and Wednesdays from 9:30 to 11:00 in room 2-102. The first lecture will be on Wed Sept 6th. There will be no class on Monday Oct 23rd (FOCS) and on Monday Oct 30th.

Instructor: Michel Goemans, room 2-351.

Topic: The topic of this course/seminar is on the embedding of finite metric spaces into normed spaces, and its applications to algorithmic problems. This is a field with lots of developments in the last 5 years, and the goal is to cover some of them.

Format: Lectures will be given by the instructor (including the first few) as well as by the participants. Participants will also be expected to take turns to scribe lecture notes. Template.

Syllabus. Here is a very preliminary and very partial list of topics.

Problem Sets:

Schedule and Scribed Lecture Notes: