Princeton University
Computer Science Dept.

Computer Science 522
Advanced Complexity Theory

Sanjeev Arora

Fall 2011

General Information | Assignments | Handouts | Interesting Links|

Jan 9: Course final has been posted; check the piazza announcement. 48-hour takehome; due Jan 15 or earlier.

Course Summary

The course starts by laying the  basic framework and results of computational complexity theory and then studies in detail some of the achievements of the past two decades, such as:

Towards the end we will put draw upon the expertise we have built up over the term to understand recent results such as Ryan Williams' 2011 result separating NEXP from ACC0.

Prerequisites: COS 340/341 or equivalent math background (basically, ability to do math proofs). Some exposure to theory of computation at an undergrad level is recommended, though not essential.
Interested undergrads should contact the instructor. Undergrads and grads will be graded separately.

About this course

Text:  Computational Complexity: A Modern Approach by Arora and Barak. Required. Try to get the latest printing (Jan 2011); it corrects many typos from earlier printings.

Grading: 60% of the grade will be based upon assignments, which will be handed out every two weeks. 40% will be based upon a long take-home final (open book).
Every student taking the course will have the responsibility to grade the homework once during the term, under my supervision.

There might also be a small course project at the end of the semester.

Administrative Information

Lectures: Tues-Thurs 3-4:20pm, Room: TBA.
Coffee half-hour after class on Thurs (optional).

Professor: Sanjeev Arora - 307 CS Building - 258-3869 Office hrs: Tue 2-3pm,  or by appointment. (Or try dropping by any afternoon.) 


Lecture notes

These are the instructor's notes (to himself) about what topics were covered in each lecture.The goal is solely to help the students (and the instructor!) recall the contents of
each lecture.

  1. Lecture 1: The Turing Machine model. P, NP, NP-completeness.
  2. Lecture 2: Diagonalization. Time Hierarchy Theorem. Nondeterministic Time Hierarchy Theorem. Why diagonalization alone wont resolve P vs NP.
  3. Lecture 3:
  4. Lec 4
  5. Lec 5
  6. Lec 6
  7. Lec 7
  8. Lec 8
  9. Lec 9
  10. Lec 10
  11. Lec 11
  12. Lec 12
  13. Lec 13
  14. Lec 14
  15. Lec 15
  16. Lec 16
  17. Lec 17
  18. Lec 18
  19. Lec 19


Honor Code for this class

Collaborating with your classmates on assignments is encouraged (and may be essential to get the most out of the course). You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.