In the table below, ``text'' refers to Sanjeev Arora's and Boaz Barak's Computational Complexity: A Modern Approach printed textbook.
Reading material labeled with ★ is optional.
| DATE | MEETING | READING |
|---|---|---|
| Lecture 1 Feb 4 |
Welcome! Introduction to the course's topics The P and NP complexity classes, the P vs NP problem. Approaches for proving P ≠ NP (diagonalizations, circuit lower bounds). |
text §1,2,3 ★Avi's book §2,3 |
| Lecture 2 Feb 6 |
Benefiting from P ≠ NP (cryptography, hardness vs randomness). Proof systems (PCP, IP=PSPACE, zero knowledge). |
|
| Lecture 3 Feb 11 |
Interactive Proofs Ex: Graph Non-Isomorphism (§8.1.3), Quadratic Non-Residuosity (ex 8.9). Goldwasser-Sipser GNI protocol (thm 8.13), the AM complexity class (§8.2). |
text §8 | Lecture 4 Feb 13 |
The complexity class IP (§8.2.1). The complexity class #P (informal ★§17.2). #SAT ⊆ IP and the SumCheck protocol (§8.3.1, 8.3.2). |
text §8,★17.2 |
| Lecture 5 Feb 18 |
The SumCheck protocol - soundness (§8.3.2). The complexity classes PSPACE and NPSPACE (def 4.1, §4.1.1). IP ⊆ PSPACE. |
text §8,4.1 |
| Lecture 6 Feb 20 |
TQBF is PSPACE-complete (statement only, thm 4.13). PSPACE and two-players games (§4.2.2). PSPACE ⊆ IP (thm 8.19). Program checking (§8.7). |
text §8,4 |
| Lecture 7 Feb 25 |
Complexity classes' diagram. Survey of IP related topics. Def: Honest verifier zero knowledge. Ex: Honest verifier zero knowledge protocol for GNI. Def: Perfect zero knowlege (PZK) (def 9.14). Ex: PKZ protocol for Graph Isomorphism (ex 9.15). |
text §9.4 Lecture notes by Ran Canetti and Alon Rosen (§3, until §3.1) Lecture notes by Rafael Pass and Abhi Shelat (§4) |
| Lecture 8 Feb 27 |
Ex: PKZ protocol for Graph Isomorphism - analysis (ex 9.15). Def: Computational zero knowledge (CZK). CZK protocol for 3COLORING (implying NP ⊆ CZK). Survey of ZK applications. |
Lecture notes by Ran Canetti and Alon Rosen (§3, until §3.1) Lecture notes by Rafael Pass and Abhi Shelat (§4) |
Lecture 9 March 3 |
The PCP Theorem Definitions and statement of the PCP thm (def 11.4, thm 11.5). Easy direction of the PCP thm: PCP[O(logn, O(1))] ⊆ NP. Ex: GNI ∈ PCP[poly(n),1] (ex 11.7). Optimization problems, approximation algorithms (def 11.1). Ex: MAX-Vertex-Cover 2-approx (ex 11.3), MAX-3SAT 7/8-approx (ex 11.2). |
text §8,11 |
| Lecture 10 March 5 |
Gap problems (definition 11.13). NP-hardness of Gap-3SAT implies hardness of approx for MAX-3SAT. The PCP Theorem as the NP-hardness of Gap-3SAT (section 11.3.1). |
Lecture notes 1 by Dana Moshkovitz |
| Lecture 11 March 10 |
Ex: Hardness of approx for independent set (section 11.4). Definition of two-provers game. The PCP theorem as two-provers one-round game. |
Lecture notes by Boaz Barak |
| Lecture 12 March 12 |
The PCP theorem as two-provers one-round game. The two-provers parallel repetition theorem (statement only) and strong PCP. Error correcting codes, linear error correcting codes. The Hadamard error correcting code. |
Lecture notes by Boaz Barak |
FALL BREAK |
| Lecture 13 March 24 |
Thm: NP ⊆ PCP[O(log(n)),polylog(n)]. Proof Step 1 - NP ⊆ PCP[O(n),O(n)], verifier performs quadratic tests. Proof Step 2 - NP ⊆ PCP[O(log(n)),O(n)], verifier performs quadratic tests. Low degree extensions. |
Lecture notes 2 by Dana Moshkovitz |
| Lecture 14 March 26 |
Proof Step 3 - PCP for Sum Check. Line vs. point low degree test (overview only). |
Lecture notes 2 by Dana Moshkovitz ★Lecture notes 3 by Dana Moshkovitz |