Princeton University Computer Science Dept.

Computer Science 522 Advanced Complexity Theory Sanjeev Arora

Fall 2011

Directory
General Information | Assignments | Handouts | Interesting Links|

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:

• approaches to the famous P vs NP question, an understanding of why they are stuck, and ideas for making future progress 
• new probabilistic definitions of classical complexity classes (IP = PSPACE and the PCP Theorems) and their implications for the hardness of computing approximate solutions to field of approximation algorithms;
• a theory of derandomization and pseudorandomness based upon computational hardness; beautiful constructions of pseudorandom objects such as extractors and expanders, and their uses in complexity theory
  
• Shor’s algorithm to factor integers using a quantum computer;
  

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 arora@cs.princeton.edu Office hrs: Tue 2-3pm,  or by appointment. (Or try dropping by any afternoon.) 

ALL COURSE HANDOUTS ARE IN ADOBE ACROBAT FORMAT. DOWNLOAD ACROBAT READER HERE.

---

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
20. 
    

 

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.