Computational Complexity
Subhash Khot

Spring 2009

General Information and Announcements

Keep looking for updates. It is your responsibility to watch out for announcements regarding homeworks, exams, handouts etc. No emails will be sent.


Homework 3 and take-home end-term are now online. Both due on May 4.

A list of candidate course projects.


Prior knowledge of following materials is assumed. A brief overview of basics will be given in the first lecture. Other than this, the course should be self-contained.

References for this basic material are :

Administrative Information

Lectures: Mon 7:10-9:00,  WWH 312

Professor: Subhash Khot – WWH 416 , 212-998-4859,   Office hours : Mon 6-7 pm.

Course Syllabus

The first part of the course will cover basic aspects of complexity theory. This includes complexity classes P, NP, L, NL, PSPACE, Polynomial Hierarchy, BPP, P/poly, NC, IP, AM, #P and relationships among them.

The second part of the course will cover advanced toipcs, e.g. PCPs, circuit lower bounds, communication complexity, derandomization, property testing and quantum computation. The emphasis will be on breadth rather than covering any of these topics in depth. We will introduce a specific topic, give a broad overview of results, and only a glimpse of the techniques. During this part of the course, you would need to read a couple of advanced research papers/surveys and write a report.


Homeworks and Exams








References and Textbooks

We will not "follow" any particular textbook. You may want to refer to :

Course notes from similar courses taught at Princeton and UC-Berkeley would be useful. See :