Advanced Complexity Theory Announcement
Audience:
This course is intended for graduate students studying the theory of
computation.
Prerequisites:
Most of the prerequisite knowledge for this class is contained in 18.404.
However, this class will be an order of magnitude more difficult.
If you didn't find 18.404 easy, you shouldn't expect to pass this class.
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.
Curriculum:
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.
Want to know more?
This is a link to the Underground Guide to Course 6 page for this course.
Daniel A. Spielman
Last modified: Mon Jan 31 15:53:11 2000