## 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.