| # | Date | lecture topic | reading | pset | |
|---|---|---|---|---|---|
| 1 | 08-22 | T | Introduction (pdf, mp4 (2021)) | Sipser §0-1.2, §3 | |
| 2 | 08-24 | R | Time complexity, def of P (pdf, mp4 (2021)) | Sipser §7.1-7.2 | pset1 (tex/pdf) |
| 3 | 08-29 | T | Non-determinism (pdf, mp4 (2021)) | Sipser §7.3 | |
| 4 | 08-31 | R | Non-determinism (pdf, mp4 (2021)) | Sipser §7.4 | |
| 5 | 09-05 | T | Non-determinism (pdf, mp4 (2021)) | Sipser §7.4 | |
| 6 | 09-07 | R | Space (pdf, mp4 (2021)) | Sipser §8.0 | pset1 due (soln). pset2 (tex/pdf) |
| 7 | 09-12 | T | Space (pdf, mp4 (2021)) | Sipser §8.1-8.3 | |
| 8 | 09-14 | R | Space (pdf, mp4 (2021)) | Sipser §8.3-8.4 | |
| 9 | 09-19 | T | Space (pdf, mp4 (2021)) | Sipser §8.5-8.6 | |
| 10 | 09-21 | R | Intractability (pdf, mp4 (2021)) | Sipser §9.1 | pset2 due (soln). pset3 (tex/pdf) |
| 11 | 09-26 | T | Intractability (pdf, mp4 (2021)) | Sipser §9.2 | |
| 12 | 09-28 | R | Circuits (pdf, mp4 (2021)) | Sipser §9.3, AB §6 | |
| 13 | 10-03 | T | Circuits (pdf, mp4 (2021)) | AB §6 | |
| 14 | 10-05 | R | Alternation (pdf, mp4 (2021*)) | Sipser §10.3, AB §5.0-5.3 | pset3 due (soln) |
| 15 | 10-10 | T | Alternation (pdf, mp4 (2021*)) | AB §5.5,6.4 | |
| 16 | 10-12 | R | Randomness (pdf, mp4 (2021*) [same mp4 as for lecture15]) | Sipser §10.2, AB §7 | pset4 (tex/pdf) |
| 17 | 10-17 | T | Randomness (pdf, mp4 (2021)) | AB §7.5 | |
| 18 | 10-19 | R | Randomness (pdf, mp4 (2021)) | Sipser §10.2 | |
| 19 | 10-24 | T | Counting (pdf, mp4 (2021)) | AB §17 | |
| 20 | 10-26 | R | Counting (pdf, mp4 (2021)) | AB §17 | pset4 due . pset5 (tex/pdf) |
| 21 | 10-31 | T | Interaction (pdf, mp4 (2021*)) | Sipser §10.4 | |
| 22 | 11-02 | R | Interaction (pdf, mp4 (2021*)) | Sipser §10.4 | |
| 23 | 11-07 | T | Interaction (pdf, mp4 (2021*)) | Sipser §10.4 | |
| 24 | 11-09 | R | Query Complexity (pdf, mp4 (2021)) | AB §12 | pset6 (tex/pdf) |
| 25 | 11-14 | T | Communication Complexity (pdf, mp4 (2020)) | AB §13 | |
| 26 | 11-16 | R | Circuit Complexity (pdf, mp4 (2020)) | AB §14; pdf | pset5 due |
| 27 | 11-28 | T | Circuit Complexity (pdf, mp4 (2020)) | AB §14; pdf | |
| 28 | 11-30 | R | Natural Proofs (pdf, mp4 (2020)) | AB §23 | pset6 due |
| 12-05 | T | Project Presentations |