Prof. Salil P. Vadhan
Course Schedule, Readings, and Assignments
| Day | Date | Topic | Arora-Barak Reading | Other Reading & Handouts | Problem Sets |
|---|---|---|---|---|---|
| Tu | 1/27 | Overview and Model of Computation | Intro, 0, 1 | ps0 | |
| Th | 1/29 | Hierarchy Theorems | 3.1, 3.2 | ||
| Tu | 2/4 | Relations between Resources, P vs NP, Reductions, Boolean Circuits | 2, 6.1, 6.2 | spr10-lec3 | |
| Th | 2/6 | Boolean Circuits, (N)P-completeness, NP vs. co-NP | above, 3.3 | spr10-lec4 | ps0 due (Fri) ps1 |
| Tu | 2/11 | Space Complexity: L,NL | 4.0,4.1,4.3 | spr10-lec5 | |
| Th | 2/13 | Space Complexity: PSPACE, Alternation, PH | 4.2, 5.0-5.3 | spr10-lec6 | |
| Tu | 2/18 | PH, Time-Space Tradeoffs for SAT | 5.4,5.5 | spr10-lec7 | |
| Th | 2/20 | Provably Intractable Problems | spr10-lec8, Sipser 9.1 |
ps1 due (Fri) ps2 |
|
| Mo | 2/24 | Add/Drop Date | |||
| Tu | 2/25 | No Class - Salil away | |||
| Th | 2/27 | No Class - Salil away | |||
| Tu | 3/4 | Relativization, Basic Circuit Complexity: P/poly | 3.4, 6.0-6.4 | spr10-lec9 | |
| Th | 3/6 | Circuit Depth: NC, AC | 6.5-6.7 | spr10-lec10 | ps2 due (Fri) |
| Tu | 3/11 | Randomized Computation: BPP, RP, ZPP | 7.0-7.4 | spr10-lec11 | |
| Th | 3/13 | BPP in PH, BPP in P/poly | 7.5 | spr10-lec12 §1-4 | ps3 |
| Tu | 3/18 | No class - Spring Break | |||
| Th | 3/20 | No class - Spring Break | |||
| Tu | 3/25 | Promise Problems (prBPP), Randomized Reductions | 17.4.1 | spr10-lec12 §5, spr10-lec13 §1 | |
| Th | 3/27 | Complexity of Counting: #P | 17 | spr10-lec13 §2, spr10-lec14 | ps3 due (Fri) ps4 |
| Tu | 4/1 | Approximate Counting & Sampling | 17.3.2 | spr10-lec15 | |
| Th | 4/3 | Average-Case Complexity | 8.6.2 | spr10-lec16 | |
| Tu | 4/8 | Interactive proofs: IP | 8.1, 8.3 | spr10-lec17 | |
| Th | 4/10 | Arthur-Merlin games: AM, MA | 8.4, 8.6, 8.2 | spr10-lec18 | ps4 due (Fri) ps5 |
| Tu | 4/15 | AM vs. IP, AM vs. PH | 8.2 | spr10-lec19 | |
| Th | 4/17 | PCPs and Hardness of Approximation | 11.0-11.3 | spr10-lec20 | |
| Tu | 4/22 | NP in PCP(poly(n),O(1)) | 11.5 | spr10-lec21 | |
| Th | 4/24 | Linearity Testing, More Inapproximability | 11.4 | spr10-lec22, spr10-lec23 §1 | ps5 due (Fri) ps6 |
| Tu | 4/29 | Review Lecture | zoo.jpg | ||
| Th | 5/1 | Reading Period | 10.0-10.2.0, 10.3 | spr10-lec26.pdf | |
| Tu | 5/6 | Reading Period | 10.6 | spr10-lec27.pdf | |
| Th | 5/8 | Reading Period | ps6 due (Fri) |
