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.
Homework:
Handouts:
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.