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 (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
Text: Computational 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 gkol@princeton.edu
TA: Sumegha Garg
- 103C CS Building sumeghag@princeton.edu
Schedule and Readings
| 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) - 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). - 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). - 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. - 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.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.