(Fall 2023) CS 581 -- Theory of computation
Schedule
Schedule (subject to change)
| Week | Date | Topic | Reading & Note |
|---|---|---|---|
| 1 | T,09/26 | Intro Math Review |
Widgerson Chapter 20 S3 Chapter 0 |
| Th,09/28 | Math proofs | S3 0 | |
| 2 | T,10/03 | Finite automata Regular expressions |
S3 1 |
| Th,10/05 | NFA Pushdown automata |
S3 1.2,2.2 | |
| 3 | T,10/10 | Turing Machines | S3 3.1 |
| Th,10/12 | TM Variants Decidability |
S3 3.2,4 | |
| 4 | T,10/17 | Reducibility | S3 5.1,5.3 |
| Th,10/19 | Time complexity P,NP |
S3 7.1-7.3 | |
| 5 | T,10/24 | Karp reduction NPC |
S3 7.4 |
| Th,10/26 | Cook-Levin More NPC |
S3 7.4,7.5 | |
| 6 | T,10/31 | Beyond NP Time hierarchy |
AB 2.6,3.1 draft book S3 9.1 |
| Th,11/02 | NP-Intermediate Relativization |
S3 6.3,9.2 AB 3.4 |
|
| 7 | T,11/07 | Limits of Diag. Space complexity |
AB3.5 S3 8.1-8.2 |
| Th,11/09 | PSPACE L,NL |
S3 8.3-8.5 | |
| 8 | T,11/14 | Randomized computation | S3 10.2 AB 7.1-7.3 Probability review note |
| Th,11/16 | BPP and friends | S3 10.2 AB 7.4,7.5 | |
| 9 | T,11/21 | Interactive proofs | S3 10.4 |
| Th,11/23 | Thanksgiving | ||
| 10 | T,11/28 | IP cont’d | AB 8.1-8.4 |
| Th,11/30 | Selected topic | ZK Note PDF |