The schedule below lists the topic of each lecture, with links to relevant notes, slides, and lecture videos. "AC" refers to Automata and Computability by Dexter Kozen, while "ToC" refers to Theory of Computation, by Dexter Kozen. **All future lecture topics are subject to change, but exam dates are not.**

**Videos of all past lectures are available on a separate page.** University login required.

- Tues Aug 29
- Administrivia, Cardinality, Diagonalization, Cantor-Schroeder-Bernstein Theorem

**Material:**lecture slides, cardinality notes, Pages 230-231 of AC

**Background Reading:**Lecture 2 of AC - Thurs Aug 31
- Regular Languages: Deterministic, Nondeterministic, Universal, and 2-way machines

**Material:**Finite automata notes, Lectures 3,4,5,6,17, and 18 of AC and Miscellaneous Exercise 61 from AC. **Homework 1 and Quiz 1 released**- Tues Sep 05
- Turing Machines and variants; Equivalence of deterministic and nondeterministic Turing machines

**Material:**Notes, Lectures 28, 29, and 30 of AC. - Thurs Sep 07
- Undecidability and Reductions

**Material:**Lectures 31, 32, and 33 of AC. **Quiz 2 released**- Tues Sep 12
- Reductions and Completeness

**Material:**Lectures 33 of AC. - Thurs Sep 14
- Rice's Theorem

**Material:**Lecture 34 of AC. **Homework 1 due. Homework 2 and Quiz 3 released**- Tues Sep 19
- Recursion Theorem
**Material:**Lecture 33, and 34 of ToC. - Thurs Sep 21
- Isomorphism Theorems: Myhill and Rogers

**Material:**Lecture 34, Miscellaneous Exercises 107, 108, and 109 of ToC. **Quiz 4 released**- Tues Sep 26
- Post's Theorem

**Material:**Lecture 37 of ToC. - Thurs Sep 28
- Oracle Turing machines and Arithmetic Hierarchy
**Material:**Lecture 35, 36 of ToC, Supplementary Lecture J of AC. **Homework 2 due. Homework 3 released****Tues Oct 03****Midterm 1: 7pm to 9pm.**- Thurs Oct 05
- Time and Space Complexity Classes
**Material:**Lecture 2 of ToC. **Quiz 5 released**- Tues Oct 10
- Savitch's Theorem
**Material:**Lecture 2 of ToC. - Thurs Oct 12
- Hierarchy Theorems
**Material:**Lecture 3 of ToC. **Homework 3 due. Homework 4 and Quiz 6 released**- Tues Oct 17
- Nondeterministic Logspace
**Material:**Lecture 4 and 5 of ToC. - Thurs Oct 19
- The Circuit Value Problem
**Material:**Lecture 6 of ToC. - Tues Oct 24
- Structure within NP: Ladner Theorem
**Material:**Section 14.1 of Computational Complexity by Papadimitriou (copy posted on Moodle) - Thurs Oct 26
- Structure within NP: Ladner Theorem (continued), Isomorphism conjecture, Berman/Mahaney Theorem.
**Material:**Section 14.1 and 14.2 of Computational Complexity by Papadimitriou (copy posted on Moodle) **Homework 4 due. Homework 5 released****Tues Oct 31****Midterm 2 on November 1: 7pm to 9pm.**- Thurs Nov 02
- Alternation
**Material:**Lecture 7 of ToC **Quiz 7 released**- Tues Nov 07
- PSPACE and Polynomial Time Hierarchy
**Material:**Lecture 8 and Lecture 9 of ToC - Thurs Nov 09
- Polynomial Time Hierarchy
**Material:**Lecture 9 and 10 of ToC **Homework 5 due. Homework 6 and Quiz 8 released**- Tues Nov 14
- Parallel Complexity
**Material:**Lecture 11 of ToC - Thurs Nov 16
- Relation of NC to Time-Space Classes
**Material:**Lecture 12 of ToC **Nov 20 to Nov 24****Thanksgiving Break**- Tues Nov 28
- Probabilistic Complexity
**Material:**Lecture 13 of ToC - Thurs Nov 30
- BPP and the Polynomial Time Hierarchy
**Material:**Lecture 14 of ToC **Homework 6 due..**- Tues Dec 05
- Interactive Proofs
**Material:**Lecture 15 of ToC - Thurs Dec 07
- Completing Lund-Fortnow-Karloff-Nisan Theorem: #SAT in IP; course wrapup and ICES forms
**Material:**Lecture 16 and 17 of ToC **Quiz 9 released**- Tues Dec 12
- Shamir's Theorem: IP=PSPACE.
**Material:**Lecture 16 and 17 of ToC **Mon Dec 18****Final exam**, 8:00am-11:00am