Princeton University Logo
Princeton University
Computer Science Dept.

Computer Science 522
Advanced Complexity Theory

Sanjeev Arora

Spring 2016






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:

Time permitting, we will discuss open problems and ongoing research.

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.

Students who wish to explore an advanced topic can substitute one homework with a small reading project (with a 3-page report).



Administrative Information

Lectures: Mon-Wed 3-4:20pm, Room: 302
Coffee half-hour after class on Wed (optional).

Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu Office hrs: Wed 2-3pm,  or by appointment. (Or try dropping by any afternoon.) 


Lecture notes and Readings

Date; Lecture topoc
Required reading
Optional Reading
Feb 1: Introduction to course topics. Turing machine Model, Universal TMs,
Definition of P.
Chapter 1 of text.

Feb 3: P vs NP; NP-completeness and its importance
Chapter 2 of text.

Feb 8: Diagonalization. Time Hierarchy Thm and Nondeterministic Time Hierarchy.
Chapter 3. (Section 3.3, Ladner's Thm, is optional)
Fortnow and Santhanam's new, more efficient proof of Nondeterministic Time Hierarchy Theorem.
Feb 10: More remarks about diagonalization. Space complexity.
Chapter 4

Feb 15: Alternation. Polynomial Hierarchy (bounded # of rounds of alternation). PSPACE (polynomial # of rounds of alternation). Connection to 2-person games.
Chapter 5, plus relevant sections of Chapter 4 on PSPACE-completeness.

Feb 17: Circuit complexity. (Running theme: Using PH to explore complexity phenomena.)
Chapter 6.

Feb 22: Randomized Computation, RP, coRP, BPP. BPP is in PH.
Chapter 7.

Feb 24: Finish randomized computation; start Interactive proofs. Definition, robustness of model, private vs public coins etc.
Chapter 8 up to section 8.2.
Babai's survey on Email and the unexpected power of interaction.
Feb 29: Interactive proofs for #SAT; sketch of IP =PSPACE.  Begin discussion of PCP Theorem
Chapter 8 (but 8.3.3 is optional)

Mar 2: Weak form of PCP Thm: NP is in PCP(poly(n), 1).
Chapter 11.
A history of the PCP Theorem by Ryan O'Donnell. (Informal notes.) For the record, I don't recall any nude bungee jumping at that 1992 conference.
Mar 7: Circuit lower bounds: Lower bounds for ACC(q) circuits.
Chapter 14.2
We didn't talk about a large research effort on proving lower bounds for algebraic circuits more generally; see the 2010 survey by Shpilka and Yehudayoff.
Mar 9: More circuit lower bounds: Razborov lower bound for monotone circuits.
Chapter 14.3

Mar 21: Cryptography: Meaning of encryption and its security. One way functions and pseudorandom generators. Equivalence to next-bit unpredictability.
Chapter 9
Cryptography textbooks by Goldreich, or Katz and Lindell, or Boneh and Shoup.
Mar 23: Cryptography (contd): Goldreich-Levin theorem; pseudorandom functions; partial derandomization of BPP using PRG's.
Chapter 9.

Mar 28: Hardness amplification. Yao's XOR lemma.
Chapter 19.1
Yao's lemma at first seems like it should be greatly improveable but it is known that some of the intuitive conjectures are wrong. See this paper by Shaltiel.
Mar 30: Hardness vs Randomness. Nisan-Wigderson generator. Derandomization under complexity theoretic assumptions. Chapter 20.1, 20.2
A 2007 survey by Impagliazzo on Hardness vs Randomness.
Apr 4: Expanders and their pseudorandom properties. Reingold's theorem (logspace algorithm for undirected connectivity). Chapter 21.1, 21.4
21.2 was touched upon but not explained in class. Some of the definitions (eg replacement product) are in 21.3

Expander graphs and their applications by
Hoory, Linial, Wigderson.
(JAMS 2006).
Apr 6: Dinur's proof of PCP Theorem.
22.1, 22.2

Apr 11: Finish Dinur's proof (including the alphabet reduction.) Fourier transforms. Use to prove correctness of linearity test.
22.3, 22.4, 22.5

Apr 13: Quantum computing: the model. Simon's algorithm for detecting the period.
10.1, 10.2, 10.3, 10.5
10.2.1 (EPR paradox) is optional but recommended. 10.6 (Shor's algorithm) was only sketched.
Apr 18: More advanced use of fourier transforms in PCPs. Long code test. Unique games conjecture and PCPs.
22.6, with a peek at 22.9.4
Khot's survey on Unique Games Conjecture and its implications.
April 20: Counting Complexity, and Toda's Theorem. Implications for circuit complexity.
Chapter 17 (but 17.3.1 and 17.3.2 are optional)

April 25: Guest lecture by Avi Wigderson on Natural Proofs (why we are stuck at proving circuit lower bounds).
Chapter 23

April 27: Another guest lecture by Avi Wigderson.


 


HOMEWORK

  1. HW 1. Questions 2.9, 2.22, 2.30, 3.2, 3.3., 3.4,  4.5. Out: Feb 10. Due: Feb 19.
  2. HW 2. Questions 5.6, 5.9, 6.3, 6.5, 6.17, 7.5, 7.7, 7.8, 8.9. Out: Feb 25; Due: Mar 7 in class.
    (Extra questions to look over but not turn in: 4.9, 8.3.)
  3. HW 3. Questions 8.6, 9.6, 9.10, 9.12, 14.6, 14.7. Out: Mar 24; Due April 1.
    (Extra questions to look over but not turn in: 9.8, 9.14)
  4. HW 4. 19.3, 20.4, 21.14, 21.20, 22.12, 22.16 (hint: needs expanders). Out: April 18; Due: April 29.
    (Extra questions to look over but not turn in: 19.1, 19.2, 20.1, 21.11,



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.