Princeton
University
|
COS 522/MAT 578
|
|
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:- Why is the P vs NP problem so important? How can we possibly prove P ≠ NP and why are we getting stuck? (diagonalization, circuit lower bounds, barriers)
- Does randomness really allows for more efficient algorithms? (de-randomization)
- How can you convince someone that you have solved a Sudoku puzzle without revealing anything about the solution (zero knowledge proofs)
- Does every theorem have a proof that can be verified by only reading two of its symbols? (Yes!! PCP and hardness of approximation)
- How can we delegate a hard computation to the cloud and verify its answer? (IP = PSPACE and other complexity classes)
- How can a quantum computer break most cryptosystems? (Quantum computing)
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 of the text suggested below, to be comfortable with following definitions and concepts: algorithms and asymptotic running time, Turing Machines, the classes P and NP, NP completeness, reductions.
About This Course
Text: Computational Complexity: A Modern Approach by Arora and Barak. A draft of the book is available here, but you should get a copy of the published book. All references to `text' below, refer to the printed version of the book.Students are encouraged to also read this inspiring book by Avi Wigderson.
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%.
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).
Administrative Information
Lectures: Tue-Thu 3-4: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 5-6pm, vidhyar@cs.princeton.edu
Qipeng (Kevin) Liu
Schedule and Readings
| 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 Non-Isomorphism (section 8.1.3) and Quadratic Non-Residuosity (example 8.9). - The Goldwasser-Sipser 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 PSPACE-complete (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: 2-approximation for MAX-Vertex-Cover (example 11.3), 7/8-approximation for MAX-3SAT (example 11.2). - Gap problems (definition 11.13). |
Chapter 11 of text. |
| Lecture 9, March 5 |
Topic: The PCP Theorem (cont'd) - NP-hardness of Gap-3SAT implies hardness of approximation for MAX-3SAT. - The PCP Theorem as the NP-hardness of Gap-3SAT (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 two-provers game. - The PCP theorem as two-provers one-round game. - Fortnow-Feige counterexample to perfect parallel repetition. |
Lecture notes by Boaz Barak here. |
| Lecture 11, March 12 |
Topic: The PCP Theorem (cont'd) - The two-provers 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). - Goldwasser-Micali Commitment Scheme based on Quadratic Residuosity. - Survey of ZK applications (enforcing good behavior in cryptographic protocols, identi cation 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). - Karp-Lipton 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) - Karp-Lipton Theorem (cont'd). - Random functions require circuits of size Ω(2n/n) (section 6.5). - The classes AC0. - Theorem: PARITY ∉ AC0 (thm 14.1). |
Chapters 6,14.1 of text. | Lecture 18, April 11 |
Topic: Circuit Lower Bounds (cont'd) - Proof of PARITY ∉ AC0 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 (Razborov-Smolensky): For distinct p,q primes, modp ∉ ACC0(q) (thm 14.4). - Proof of every ACC0(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 low-degree polynomial (section 14.2). - Karchmer-Wigderson 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 1-bit 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 Nisan-Wigderson PRG (definition 20.12, lemma 20.15). - Kabanets-Impagliazzo Theorem (thm 20.17, statement only). |
Chapter 20 of text. | Lecture 24, May 2 |
Topic: Hardness vs Randomness (cont'd) - Extractors definitions: min-entropy, sources (definition 21.22), seeded extractors (definition 21.24). - Extractors with logarithmic seeds exist (thm 21.25, statement only). - Trevisan's Extractor based on Nisan-Wigderson PRG (section 21.5.7). - Natural Proofs (Razborov-Rudich): 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. |
Problem Sets
Problem Set 1 - out: March 1, due: March 14.Problem Set 2 - out: March 22, due: April 4.
Problem Set 3 - out: April 14, due: April 25.
Problem Set 4 - out: May 4, due: May 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.