(Fall 2021) CS 581 - Theory of computation
Schedule (subject to change)
General guideline
- Zoom link to join lectures remotely, TR 14:00 - 15:15.
Schedule (subject to change)
| Week | Date | Topic | Reading & Note |
|---|---|---|---|
| 1 | T,09/28 | Intro Warmup: finite automata |
W Chapter 20, AB Chapter 0,1.1 Barak note, Watrous note |
| Th,09/30 | Review: Turing machines | AB 1.2-1.5 | |
| 2 | T,10/05 | Time complexity P, NP |
AB 1.6,2.1 |
| Th,10/07 | NPC | AB 2.2,2.3 | |
| 3 | T,10/12 | More NPC | AB 2.3,2.4 |
| Th,10/14 | Self reducibility | AB 2.5 | |
| 4 | T,10/19 | Beyond NPC Time hierarchy |
AB 2.6,1.5,3.1 |
| Th,10/21 | Ladner’s theorem | AB 3.3 | |
| 5 | T,10/26 | Nondeterminism Relativization |
AB 3.2,3.4 |
| Th,10/28 | Space complexity | AB 4.1-4.3 | |
| 6 | T,11/02 | Space complexity cont’d | AB 4.1-4.3 |
| Th,11/04 | Polynomial hierarchy | AB 5.1,5.2 | |
| 7 | T,11/09 | Randomized computation | AB 7.1-7.3 |
| Th,11/11 | Veterans day No Class |
Review probability basics AB A.2, Trevisan’s note |
|
| 8 | T,11/16 | BPP and more | AB 7.4-7.6 |
| Th,11/18 | Interactive proofs | AB 8.1,8.2 | |
| 9 | T,11/23 | Interactive proofs | AB 8.3 |
| Th,11/25 | Thanksgiving No Class |
||
| 10 | T,11/30 | Zero-knowledge proofs | AB 9.4 |
| Th, 12/02 | Selected topics Wrap-up |