(Fall 2022) CS 581 -- Theory of computation
Schedule
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/27 | Intro Math Review |
Widgerson Chapter 20 S3 Chapter 0 |
| Th,09/29 | Math proofs | S3 0 | |
| 2 | T,10/04 | Finite automata Regular expressions |
S3 1 |
| Th,10/06 | NFA Pushdown automata |
S3 1.2,2.2 | |
| 3 | T,10/11 | Turing Machines | S3 3.1 |
| Th,10/13 | TM Variants Decidability |
S3 3.2,4 | |
| 4 | T,10/18 | Reducibility Time complexity |
S3 5.1,5.3,7.1 |
| Th,10/20 | P,NP | S3 7.2,7.3 | |
| 5 | T,10/25 | NPC Cook-Levin |
S3 7.4 |
| Th,10/27 | More NPC Beyond NP |
S3 7.5 AB 2.6 draft book |
|
| 6 | T,11/01 | Time hierarchy NP-Intermediate |
AB 3.1 S3 9.1 AB 3.4,2.7 |
| Th,11/03 | Oracle machine Relativization |
S3 6.3,9.2 AB 3.5 |
|
| 7 | T,11/08 | Space complexity | S3 8.1-8.3 |
| Th,11/10 | L,NL | S3 8.4,8.5 | |
| 8 | T,11/15 | Randomized computation | S3 10.2 AB 7.1-7.3 Probability review note |
| Th,11/17 | BPP and friends | S3 10.2 AB 7.4,7.5 | |
| 9 | T,11/22 | Interactive proofs | S3 10.4 |
| Th,11/24 | Thanksgiving | ||
| 10 | T,11/29 | IP cont’d | AB 8.1-8.4 |
| Th,12/01 | Selected topic Review |
ZK Note PDF |