Princeton University Computer Science Dept.

Computer Science 522 Advanced Complexity Theory Sanjeev Arora

Spring 2014

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; 
• Frontier of our knowledge wrt P vs NP question.
  

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 (those who lack such a course should do self-study using Sipser's Theory of Computation or an equivalent text.)

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: 302
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 and Readings

1. Lecture 1 (Feb 4) The Turing Machine model. P, NP, NP-completeness. Chapter 1.
   
2. Lecture 2 (Feb 6) NP-completeness, meaning of P vs NP. Introduction to Polynomial Hierarchy. Chapter 2.
3. Lecture 3 (Feb 11; lecturer Zeev Dvir) Polynomial-hierarchy and alternation. Introduction to circuits. Chapter 5. (Just read up to Section 5.2 in Chapter 5 for now.)
   
4. Lecture 4. (Feb 13) Diagonalization. Chapter 3. (Section 3.3 is optional, though recommended.)
5. Lecture 5 (Feb 18)  Space Bounded Computation and Space complexity. Chapter 4.
6. Lecture 6 (Feb 20) NL =coNL. Karp Lipton Theorem.
   
7. Lecture 7 (Feb 25) Randomized computation. (Chapter 7).
   
8. Lecture 8 (Feb 27) Finish randomized computation. Odds and ends that we missed in Chapters 1--7 including Time-space tradeoff for SAT, small-depth circuits (NC) etc.
   
9. Lecture 9 (Mar 4) Interactive proofs. Variants, private vs public coins. Interactive proof for #SAT.
   
10. Lecture 10 (Mar 6) IP=PSPACE, program checking, testing, random self-reducibility etc... (Chapter 8 finished.)
11. Lecture 11 (Mar 11) Start Quantum computation. Quantum reality. Nonlocal games ( CHSH). Quantum circuits and BQP. Classical computation is a subcase.  Additional reading: Lecture notes by John Watrous on Nonlocal games.
    
12. Lecture 12 (Mar 13) Quantum fourier transform, and Shor's algorithm. (Finishes Chapter 10 except for Grover's algorithm, which is optional reading.)
13. Lecture 13 (Mar 25) Strongly hard functions and Derandomization via Nisan-Wigderson generator. (Chapter 20, Sections 20.1, 20.2. Useful reading: Yao's hybrid argument in Section 9.3.)
14. Lecture 14 (Mar 27) Amplification of hardness via Yao's XOR Lemma. (Chapter 19, Section 19.1. Also did a survey of other sections in Chapter 19 but may return to them later.)
15. Lecture 15, 16, 17 (April 1 --8) Circuit lowerbounds. Guest lecturer Avi Wigderson.  (Chapter 14)
    

 

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.