| Date | Topic |
|---|---|
| September 27 | Computational Models |
| October 2 | Turing Machines and Boolean Circuits |
| October 4 | Tight Bounds for Circuits and Counting Arguments |
| October 9 | Diagonalization |
| October 11 | Hierarchy Theorems |
| October 16 | Nondeterministic Polynomial Time |
| October 18 | NP-complete problems |
| October 23 | More NP-complete problems |
| October 25 | The problem with using Diagonalization to separate P and NP |
| October 30 | Space |
| November 1 | NL vs coNL |
| November 8 | TQBF |
| November 13 | Randomized Algorithms |
| November 20 | Randomized Complexity Classes |
| November 27 | Schwartz-Zippel and the Determinant |
| November 29 | Permanent and Interactive Proofs |
| December 5 | Course Evaluation |
| December 6 | IP=PSPACE |
| December 8 | Course Summary |