CSCIGA.3350001
Theory
of Computation (Honors)


Solutions
to Homework 1,2 and midterm are 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
selfcontained.
References
for this basic material are :
Professor: Subhash Khot – Off 416, 2129984859, 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 takehome midterm and a takehome endterm.
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 UCBerkeley may be useful. See :