of Computation (Honors)
Homework 1 and 2 are available. Due on Feb 24 and Mar 24 respectively.
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 :
Professor: Subhash Khot – Off 416, 212-998-4859, Office hours : Just before the class or by appointment.
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 Due Feb 24
Homework 2 Due Mar 24
Midterm Due Mar 26
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 http://www.cs.princeton.edu/theory/index.php/Compbook/Draft.
You may also want to refer to :
Course notes from similar courses taught at Princeton and UC-Berkeley may be useful. See :