Theory of Computation (Honors)
Subhash Khot

Spring 2014

General Information and Announcements

Homework 3 (due April 28) and Endterm (due May 12) available.  A short (= 2 page) report on your reading project (= one research paper from the list below) is also due May 12. No extensions on any of these deadlines.    


Solutions to Homework 1,2 and midterm are available.


List of papers to read.



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: MW  3:30-4:45,  WWH  312 

Professor: Subhash Khot – Off 416, 212-998-4859,   Office hours :  Just before the class or by appointment.

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.     


Homeworks and Exams

There will be three homeworks, a take-home midterm and a take-home endterm. 


Homework 1   Solutions


Homework 2   Solutions


Midterm          Solutions


Homework 3  



Towards the end of the course, you might be required to read one research paper of your choosing and present it in class.  The list of  recommended papers/topics appears above.   


References and Textbooks

We will not "follow" any particular textbook, but a good reference is:   Arora and Barak:  Computational Complexity: A Modern Approach.  

A draft of this book is available at 


 You may also want to refer to :

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