Princeton University Logo
Princeton University
Computer Science Dept.

COS 522/MAT 578
Advanced Computational Complexity

Gillat Kol

Spring 2017

Course Summary

Computational complexity theory is a mathematical discipline that studies efficient computation. The course covers some of truly beautiful ideas of modern complexity theory, showing how deep mathematics can be used to rigorously prove useful philosophical statements. We will answer questions like:

Prerequisites: COS 340/341 or equivalent math background (basically, the ability to do mathematical 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 of Section 1 and 2 (especially with Subsections 1.5; 2.1; 2.2; 2.3) of the text suggested below, to be comfortable with following definitions and concepts: algorithms and asymptotic running rime, Turing Machines, the classes P and NP, NP completeness, reductions.

About This Course

TextComputational Complexity: A Modern Approach by Arora and Barak. A draft of the book is available here. However, you should try to get the latest printing (Jan 2011); it corrects many typos from earlier printings.

Grading: The grade will be based upon assignments, which will be handed out every 2-3 weeks. 7-10 days will be given to complete each assignment. Collaborating with your classmates on assignments is encouraged, with the exception of the last assignment that should be completed alone. The last assignment will constitute for 30% of the grade and the rest of the assignments for 70%.

Administrative Information

Lectures: Tue-Thu 3-4:20pm, Room: Friend Center 005, Signup on Piazza: Link

Professor: Gillat Kol - 316 CS Building 
TA: Sumegha Garg - 103C CS Building 

Schedule and Readings

Lecture topic
Required reading
Lecture 1,
Feb 7
Introduction to Course Topics
- The P vs NP problem and its importance.
- Approaches for proving P ≠ NP (diagonalizations, circuit lower bounds).
- Benefiting from P ≠ NP (cryptography, hardness vs randomness).
Chapter 1,2 of text.
Lecture 2,
Feb 9
Introduction to Course Topics (cont'd):
- Proof systems (PCP, IP=PSPACE, zero knowledge).

Topic: Diagonalizations and the Relativization Barrier
- Proofs using diagonalizations: halting problem (thm 1.16) and Godel's first incompleteness theorem, time hierarchy (thm 3.1) and the complexity class EXP (section 2.6.2), Ladner's Theorem (thm 3.4, statement only).
- Oracle machines (section 3.5).
Chapter 3 of text.
Lecture 3,
Feb 13
Topic: Diagonalizations and the Relativization Barrier (cont'd)
- Baker-Gill-Solovay Theorem (thm 3.9).

- The complexity class #P (section 9.1).
- The complexity class IP (section 8.2) and an IP protocol for Graph Non-Isomorphism (section 8.2).
Chapters 3,8 of text.
Lecture 4,
Feb 15
Topic: IP=PSPACE (cont'd)
- (decision) #P ⊆ IP and the sumcheck protocol (sections 8.5.1, 8.5.2).
- The complexity class coNP (section 2.6.1) .
Chapter 8 of text.
Lecture 5,
Feb 21
Topic: IP=PSPACE (cont'd)
- The complexity classes PSPACE and NPSPACE: Configuration graphs (section 4.1), TQBF is PSPACE-complete (thm 4.11), Savitch's theorem (thm 4.12, statement only), PSPACE and games (section 4.3.2).
- IP ⊆ PSPACE (thm 8.17).
Chapters 4,8 of text.
Lecture 6,
Feb 23
- PSPACE ⊆ IP (thm 8.17).
- Program checking (section 8.7).
- MIP = NEXP (thm 8.26, statement only).

Topic: The PCP Theorem
- Definitions and statement of the PCP theorem PCP[O(log(n)),O(1)] = NP (section 18.1).
Chapters 8,18 of text.
Lecture 7,
Feb 28
Topic: The PCP Theorem (cont'd)
- PCP(O(logn, O(1))) ⊆ NP.
- GNI ∈ PCP(poly(n),1) (example 18.3).
- MIP = MIP[2] = PCP(poly(n), poly(n)) (theorem 6 here).
Chapters 18 of text.
Lecture notes by Dieter van Melkebeek here.
Lecture 8,
March 2
Topic: The PCP Theorem (cont'd)
- The PCP Theorem as a two provers game.
- The Fortnow-Feige counterexample for Parallel Repetition, the Parallel Repetition Theorem (statement only), the strong PCP theorem.
- Approximation algorithms and gap problems.
Chapter 18 of text.
Lecture notes by Boaz Barak here.
Lecture notes by Dana Moshkovitz here.
Lecture 9,
March 7
Topic: The PCP Theorem (cont'd)
- The PCP Theorem as the NP-hardness of Gap-3SAT.
- NP ⊆ PCP[O(log(n)),polylog(n)] : Step 1 - NP ⊆ PCP[O(n),O(n)] with a verifier that performs quadratic tests.
Lecture notes by Dana Moshkovitz here and here.
Lecture 10,
March 9
Topic: The PCP Theorem (cont'd)
- NP ⊆ PCP[O(log(n)),polylog(n)] : Step 2 - NP ⊆ PCP[O(log(n)),O(n)] with a verifier that performs quadratic tests.
- Error correcting codes, linear error correcting codes, the Hadamard code.
- Low degree extensions.
Lecture 11,
March 16
Topic: The PCP Theorem (cont'd)
- NP ⊆ PCP[O(log(n)),polylog(n)] : Step 3 - PCP for Sum Check.
- Low degree test (overview only).
Lecture notes by Dana Moshkovitz here and here.
Lecture 12,
March 28
Topic: Hardness vs Randomness
- Boolean circuits, the class P/poly, Turing machines that take advice (section 6.1).
- The Polynomial Hierarchy (sections 5.1 and 5.2).
- Karp-Lipton Theorem: NP ⊆ P/poly ⇒ Polynomial Hierarchy collapses to the second level (section 6.2).
Chapters 5,6 of text.
Lecture 13,
March 30
Topic: Hardness vs Randomness (cont'd)
- The class BPP (section 7.1).
- Examples: Finding primes, Polynomial identity testing (sections 7.2.2).
- Definition of pseudorandom distributions and pseudorandom generators (PRGs) (section 16.1).
- Using PRGs to derandomize BPP (section 16.1).
- Definition of predictors (section 10.2.1).
- ∃ predictor for a distribution D ⇒ D not pseudorandom (section 10.2.2).
Chapters 7,10,16 of text.
Lecture 14,
April 4
Topic: Hardness vs Randomness (cont'd)
- D not pseudorandom ⇒ ∃ predictor for a distribution D (section 10.2.2).
- PRG with 1-bit stretch (section 16.2.1).
- Hardness assumptions: worst case, mild, and extremely hard functions (section 16.7).
Chapters 10,16 of text.
Lecture 15,
April 6
Topic: Hardness vs Randomness (cont'd)
- The Nisan-Wigderson PRG (section 16.1.1).
- Construction of Almost Disjoint Sets (section 16.1.1).
Chapter 16 of text.
Lecture 16,
April 11
Topic: Circuit Lower Bounds
- Random functions require circuits of size Ω(2n/n) (section 6.3).
- The classes AC0 and ACC0.
- Theorem: PARITY ∉ AC0.
- Proof 1 (Razborov-Smolensky): Every AC0 can be approximated by a low degree polynomial (section 13.2).
Chapters 6,13 of text.
Lecture 17,
April 13
Topic: Circuit Lower Bounds (cont'd)
- Proof 1 (Razborov-Smolensky): PARITY cannot be approximated by a low-degree polynomial (section 13.2).
- Proof 2: PARITY ∉ AC0 using the Håstad Switching Lemma (section 13.1).
Chapter 13 of text.
Lecture 18,
April 18
Topic: Circuit Lower Bounds (cont'd)
- Proof 2: Proof of the Håstad's Switching Lemma (section 13.1).

Topic: Communication Complexity
- The deterministic communication complexity setting (section 12.1).
- The PARITY and inner product examples.
Chapter 12 of text.
Lecture 19,
April 20
Topic: Communication Complexity (cont'd)
- The Clique vs Independent Set example.
- Protocol trees.
- The randomized communication complexity setting (section 12.4).
- The Equality function example (deterministic, public-coin and private-coin communication complexity).
- Newman's Theorem: public-coin vs private-coin (statement only).
- Combinatorial rectangles.
Chapter 12 of text.
Lecture notes by Toniann Pitassi here.
Lecture 20,
April 25
Topic: Communication Complexity (cont'd)
- Deterministic communication complexity lower bounds techniques: Tiling lower bound (section 12.2.2), Fooling sets (section 12.2.1), the rank lower bound and the log-rank conjecture (section 12.2.3).
- Lower bounds for the Equality and Disjointness functions.
- Karchmer-Wigderson Games and the connection to circuit depth lower bounds (section 13.5.4).
Chapters 12,13 of text.
Lecture notes by Toniann Pitassi here.
Lecture 21,
April 27
Guest Lecture: Avi Widgerson talking about Proof Complexity.
Lecture 22,
May 2
Topic: Communication Complexity (cont'd)
- Karchmer-Wigderson theorem: Depth(f) = CC(Gf) (section 13.5.4).
- Monotone functions, monotone circuit complexity.
- Monotone Karchmer-Wigderson Games.
Chapters 13 of text.
Lecture notes by Ran Raz here.
Lecture 23,
May 4
Topic: Communication Complexity (cont'd)
- Raz-Wigderson thm: monotone-Depth(MATCHING) = Ω(n). Proof using monotone Karchmer-Wigderson Games.

Topic: Natural Proofs
- Razborov-Rudich: Assuming that one way function exists, no natural proof can show P ≠ NP (section 22).
Chapters 22 of text.
Lecture notes by Ran Raz here.

Problem Sets

Problem Set 1. Out: February 27. Due: March 7.
Problem Set 2. Out: March 20. Due: April 4.
Problem Set 3. Out: April 25. Due: May 4.
Problem Set 4. Out: May 12. Due: May 22.

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.