G22.3350-001
Honors Theory of Computation
|
|
Homework
3 and Endterm are now available.
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 – WWH 416 , 212-998-4859, Office hours : Mon 2:30-3:30.
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
If you are taking the course for credit, you must submit at least one of Homeworks 1,2,3 and at least one of Midterm, Endterm. Of course, if you want to
submit more than the required threshold, you are welcome!
Towards
the end of the course, you will be required to read one research paper of your
choosing. The list of papers/topics will be made available.
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 :