| Date | Topic | Slides | Video | Reference |
| 03/29/22 | The complexity classes P and NP | lec1 | youtube (old) | notes |
| 03/31/22 | NP-completeness and the Cook-Levin Theorem | lec2 | youtube | |
| 04/05/22 | 3SAT is NP-complete, the definition of co-NP | lec3 | youtube | |
| 04/07/22 | EXP, NEXP, Padding Arguments, and the Time Hierarchy Theorem | My notes | youtube (old) | |
| 04/12/22 | Space complexity, Savitch's Theorem, and PSPACE completeness of QBF | My notes | youtube about Savitch (old) youtube about QBF (old) | |
| 04/14/22 | NL, DPATH is complete for NL, the read once certificate characterization of NL | Notes on NL Notes on read-once cert | youtube about NL (old) youtube about read-once cert | |
| 04/19/22 | NL = co-NL | Notes on NL = co-NL | youtube (old) | |
| 04/21/22 | The Polynomial Hierarchy | Notes on PH | youtube (old) | |
| 04/26/22 | The Polynomial Hierarchy: proving equivalence of different views | lec9 | youtube | |
| 04/28/22 | Proving that Sigma-i-SAT is complete for Sigma-i, starting discussion of circuit complexity | lec10 | youtube (sigma-i-SAT) youtube (circuits) | |
| 05/03/22 | The proof of Shannon's theorem, the Karp-Lipton theorem | lec11 Old notes (Shannon's thm) | ||
| 05/05/22 | Introduction to randomized complexity classes, BPP and boosting | lec12 | youtube | |
| 05/10/22 | BPP is in P/poly, BPP is in Sigma2 | lec13 | youtube | |
| 05/12/22 | Interactive protocols, the 2-round protocol for Graph Non-Isomorphism | lec14 | youtube | |
| 05/17/22 | Arthur-Merlin protocols, the class BP.NP, and the Goldwasser-Sipser set lower bound protocol | lec15 | youtube | |
| 05/19/22 | Proving the set lower bound protocal, starting proof that #SAT is in IP, the Sumcheck protocol | lec16 | youtube | |
| 05/24/22 | Proving the correctness of the Sumcheck protocol for #SAT, a short discussion of multiple prover protocols, and the PCP connection | lec17 | youtube | |
| 05/26/22 | A high-level view of the PCP theorem and the connections to hardness of approximation | lec18 | youtube | |
| 05/31/22 | The basics of cryptography, from a complexity theoretic standpoint | lec19 | youtube | |
| 06/02/22 | Impagliazzo's five worlds, and a whirlwind tour of complexity theory | lec20 |