On The Boundary of P and NP (Spring 2011)

Lecturers: Irit Dinur and Uri Feige
Location: Ziskind 1
Time: Monday 11:00 - 13:00

The final assignment / exam is due July 22. Good luck!

Syllabus: We plan to discuss issues on the borderline between P and NP, including exponential time algorithms, algorithms for random instances, approximation algorithms, the PCP theorem and hardness of approximation, the unique games conjecture.

Prerequisites: The course assumes previous basic knowledge in algorithms, computational complexity (in particular, NP-completeness and the notion of reductions among problems), probability theory (only of finite probability spaces), and linear algebra.

Homework: The homework assignments are an important part of the course. They need to be handed in two weeks after they are given, they are a prerequisite for receiving credit in the course, and their grades will determine a substantial part of the final grade.
Lecture notes for at least some of the lectures will become available on the web.

Requirements: Attendance, homework assignments, final project.



Lecture Notes:

Lecture #1 (March 14, 2011)

Related links:

A new book on approximation algorithms by Williamson and Shmoys.
An online course of Ryan O'donnell on Analysis of Boolean functions.