Princeton
University

COS 522/MAT 578


Grading: The grade will be based upon assignments, which will be handed out every 23 weeks. 710 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%.
Lectures: TueThu 34:20pm, Room: Friend Center 005, Signup on Piazza: Link
Professor: Gillat Kol
 316 CS Building gkol@princeton.edu
TA: Sumegha Garg
 103C CS Building sumeghag@princeton.edu
Date 
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).  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)  BakerGillSolovay Theorem (thm 3.9).  The complexity class #P (section 9.1).  The complexity class IP (section 8.2) and an IP protocol for Graph NonIsomorphism (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 PSPACEcomplete (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).  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 FortnowFeige 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 NPhardness of Gap3SAT.  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).  KarpLipton 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 1bit 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 NisanWigderson 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 Ω(2^{n}/n) (section 6.3).  The classes AC^{0} and ACC^{0}.  Theorem: PARITY ∉ AC^{0}.  Proof 1 (RazborovSmolensky): Every AC^{0} 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 (RazborovSmolensky): PARITY cannot be approximated by a lowdegree polynomial (section 13.2).  Proof 2: PARITY ∉ AC^{0} 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).  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, publiccoin and privatecoin communication complexity).  Newman's Theorem: publiccoin vs privatecoin (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 logrank conjecture (section 12.2.3).  Lower bounds for the Equality and Disjointness functions.  KarchmerWigderson 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)  KarchmerWigderson theorem: Depth(f) = CC(G_{f}) (section 13.5.4).  Monotone functions, monotone circuit complexity.  Monotone KarchmerWigderson Games. 
Chapters 13 of text. Lecture notes by Ran Raz here. 
Lecture 23, May 4 
Topic: Communication Complexity (cont'd)  RazWigderson thm: monotoneDepth(MATCHING) = Ω(n). Proof using monotone KarchmerWigderson Games.  RazborovRudich: 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. 
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.