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%.
Assignments should be typed. LaTeX is strongly recommended, it's free and can be downloaded here.
Here is a suggested LaTaX template for problem sets' solutions (.tex), this is what it looks like once compiled (.pdf).
Lectures: TueThu 34:20pm, Room: Lewis Library 138, Signup on Piazza: Link
Teaching:
Gillat Kol
 194 Nassau st, Office 230 gkol@princeton.edu
TAs:
Vidhya Ramaswamy
 194 Nassau st, Office 246, Office hours: Thursdays 56pm, vidhyar@cs.princeton.edu
Qipeng (Kevin) Liu
Date 
Lecture topic 
Required reading 
Lecture 1, Feb 5 
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). 
Chapters 1,2 of text. 
Lecture 2, Feb 7 
Introduction to Course Topics (cont'd)  Benefiting from P ≠ NP (cryptography, hardness vs randomness).  Proof systems (PCP, IP=PSPACE, zero knowledge). 

Lecture 3, Feb 12 
Topic: Interactive Proofs  Examples: IP protocols for Graph NonIsomorphism (section 8.1.3) and Quadratic NonResiduosity (example 8.9).  The GoldwasserSipser public coin protocol for GNI (theorem 8.13) and the AM complexity class (section 8.2). 
Chapter 8 of text. 
Lecture 4, Feb 14 
Topic: Interactive Proofs (cont'd)  The complexity class IP (section 8.2.1).  The complexity class #P (section 17.2).  #SAT ⊆ IP and the SumCheck protocol (sections 8.3.1, 8.3.2). 
Chapter 8 of text. 
Lecture 5, Feb 19 
Topic: Interactive Proofs (cont'd)  The SumCheck protocol  soundness (section 8.3.2).  The complexity classes PSPACE and NPSPACE (definition 4.1, section 4.1.1).  IP ⊆ PSPACE. 
Chapter 8 of text. 
Lecture 6, Feb 21 
Topic: Interactive Proofs (cont'd)  TQBF is PSPACEcomplete (thm 4.13), Savitch's theorem (thm 4.14, statement only).  PSPACE and games (section 4.2.2).  PSPACE ⊆ IP (thm 8.19). 
Chapters 4 and 8 of text. 
Lecture 7, Feb 26 
Topic: Interactive Proofs (cont'd)  Program checking (section 8.7).  Survey of IP related topics (MIP=NEXP, Competing Provers=EXP, quantum delegation, delegation for muggles, delegation with distributed verifier, delegation with cryptographic assumptions).  Definitions and statement of the PCP theorem PCP[O(log(n)),O(1)] = NP (definition 11.4 and theorem 11.5). 
Chapters 8 and 11 of text. 
Lecture 8, Feb 28 
Topic: The PCP Theorem (cont'd)  Easy direction of the PCP theorem: PCP(O(logn, O(1))) ⊆ NP.  Example: GNI ∈ PCP(poly(n),1) (example 11.7).  Optimization problems, approximation algorithms (definition 11.1).  Examples: 2approximation for MAXVertexCover (example 11.3), 7/8approximation for MAX3SAT (example 11.2).  Gap problems (definition 11.13). 
Chapter 11 of text. 
Lecture 9, March 5 
Topic: The PCP Theorem (cont'd)  NPhardness of Gap3SAT implies hardness of approximation for MAX3SAT.  The PCP Theorem as the NPhardness of Gap3SAT (section 11.3.1). 
Lecture notes by Dana Moshkovitz
here. 
Lecture 10, March 7 
Topic: The PCP Theorem (cont'd)  Example: Hardness of approximation for independent set (section 11.4).  Definition of twoprovers game.  The PCP theorem as twoprovers oneround game.  FortnowFeige counterexample to perfect parallel repetition. 
Lecture notes by Boaz Barak here. 
Lecture 11, March 12 
Topic: The PCP Theorem (cont'd)  The twoprovers parallel repetition theorem (statement only) and strong PCP.  NP ⊆ PCP[O(log(n)),polylog(n)] : Step 1  NP ⊆ PCP[O(n),O(n)] with a verifier that performs quadratic tests.  Error correcting codes, linear error correcting codes. 
Lecture notes by Dana Moshkovitz
here. 
Lecture 12, March 14 
Topic: The PCP Theorem (cont'd)  The Hadamard error correcting code.  NP ⊆ PCP[O(log(n)),polylog(n)] : Step 2  NP ⊆ PCP[O(log(n)),O(n)] with a verifier that performs quadratic tests.  Low degree extensions. 
Lecture notes by Dana Moshkovitz
here. 
*** Spring Break *** 

Lecture 13, March 26 
Topic: The PCP Theorem (cont'd)  NP ⊆ PCP[O(log(n)),polylog(n)] : Step 3  PCP for Sum Check.  Line vs. point low degree test (overview only). 
Lecture notes by Dana Moshkovitz
here and
here. 
Lecture 14, March 28 
Topic: Zero Knowledge Proofs  Definition: Honest verifier zero knowledge.  Example: Honest verifier zero knowledge protocol for GNI.  Definition: Perfect zero knowlege (PZK) (definition 9.14).  Example: PKZ protocol for Graph Isomorphism (example 9.15). 
Chapter 9.4 of text. Lecture notes by Ran Canetti and Alon Rosen (section 3, until the beginning of 3.1) here. Lecture notes by by Rafael Pass and Abhi Shelat (section 4.5) here. 
Lecture 15, April 2 
Topic: Zero Knowledge Proofs (cont'd)  Definition: Computational zero knowledge (CZK).  CZK protocol for 3COLORING (implying NP ⊆ CZK).  GoldwasserMicali Commitment Scheme based on Quadratic Residuosity.  Survey of ZK applications (enforcing good behavior in cryptographic protocols, identication schemes, blockchains, electronic voting). 
Lecture notes by Ran Canetti and Alon Rosen (sections 3.3 and 3.4) here. Lecture notes by by Rafael Pass and Abhi Shelat (section 4.6) here. 
Lecture 16, April 4 
Topic: Circuit Lower Bounds  Boolean circuits and the complexity class P/poly (section 6.1).  Turing machines that take advice (thm 6.18, description only).  The Polynomial Hierarchy (section 5.2).  KarpLipton Theorem: NP ⊆ P/poly ⇒ Polynomial Hierarchy collapses to the second level (thm 6.19). 
Chapters 5,6 of text. 
Lecture 17, April 9 
Topic: Circuit Lower Bounds (cont'd)  KarpLipton Theorem (cont'd).  Random functions require circuits of size Ω(2^{n}/n) (section 6.5).  The classes AC^{0}.  Theorem: PARITY ∉ AC^{0} (thm 14.1). 
Chapters 6,14.1 of text. 
Lecture 18, April 11 
Topic: Circuit Lower Bounds (cont'd)  Proof of PARITY ∉ AC^{0} using the Switching Lemma (section 14.1.1).  Proof of the Switching Lemma (section 14.1.2). 
Chapter 14.1 of text. 
Lecture 19, April 16 
Topic: Circuit Lower Bounds (cont'd)  Proof of the Switching Lemma (cont'd).  Theorem (RazborovSmolensky): For distinct p,q primes, mod_{p} ∉ ACC^{0}(q) (thm 14.4).  Proof of every ACC^{0}(q) can be approximated by a low degree polynomial (section 14.2). 
Chapters 6,13 of text. 
Lecture 20, April 18 
Topic: Circuit Lower Bounds (cont'd)  Proof of PARITY cannot be approximated by a lowdegree polynomial (section 14.2).  KarchmerWigderson Games and the connection to circuit depth lower bounds. 
Chapter 14.2 of text. Lecture notes by Ran Raz here. 
Lecture 21, April 23 
Topic: Hardness vs Randomness  The class BPP (section 7.1).  Examples: Finding primes, volume estimation, polynomial identity testing (section 7.2.3 and example 20.1).  Definition of pseudorandom distributions and pseudorandom generators (PRGs) (definition 20.2).  Using PRGs to derandomize BPP (thm 20.3).  Definition of predictors. 
Chapters 7,20 of text. 
Lecture 22, April 25 
Topic: Hardness vs Randomness (cont'd)  ∃ predictor for a distribution D iff D not pseudorandom (thm 9.11).  PRG with 1bit stretch (lemma 20.9). 
Chapters 9,20 of text. 
Lecture 23, April 30 
Topic: Hardness vs Randomness (cont'd)  Hardness assumptions: worst case, mild, and extremely hard functions.  Construction of Almost Disjoint Sets (lemma 20.14).  The NisanWigderson PRG (definition 20.12, lemma 20.15).  KabanetsImpagliazzo Theorem (thm 20.17, statement only). 
Chapter 20 of text. 
Lecture 24, May 2 
Topic: Hardness vs Randomness (cont'd)  Extractors definitions: minentropy, sources (definition 21.22), seeded extractors (definition 21.24).  Extractors with logarithmic seeds exist (thm 21.25, statement only).  Trevisan's Extractor based on NisanWigderson PRG (section 21.5.7).  Natural Proofs (RazborovRudich): Assuming one way functions exist, no natural proof can show NP not contained in P/poly (thm 23.1, sketch only). 
Chapters 21, 23 of text. Lecture notes by Luca Trevisan (Lecture 25) 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.