Courses:

This course is intended for graduate students studying the theory of computation.

Prerequisites

Most of the prerequisite knowledge for this class is contained in Theory of Computation (18.404). However, this class will be an order of magnitude more difficult.

Course Outline

This class will survey some of the most important developments in complexity theory. After completing the class, students should be able to read and contribute to current research in the field.

A rough list of topics is

• Basic time and space classes, the polynomial-time hierarchy.
• Randomized classes: RP, BPP, RL, and their relation to PH.
• Counting classes: #P
• Non-uniform classes
• Oracles, relativization
• Interactive proof systems
• Pseudo-random generators, or do we need randomness?
• Some circuit lower bounds--monotone and AC0.

Work

There will be 4-5 problem sets during the semester. Each student will also be responsible for editing the lecture notes from two lectures. Some students will write notes for lectures that do not overlap with last year.

Readings

There is no required textbook for this course, but there is a list of recommended backgroung readings.

Grading

Grades will be determined 80% by the problem sets, and 20% by scribe notes.