8/25—Introduction, computability review

Reading: Introduction, §0–1.5.1 ipynb

8/27—Undecidability, Rice’s theorem

Reading: §0–1.5.1 notes

9/1—Gödel’s incompleteness theorem

Reading: §1.5.2

9/3—Time hierarchy theorem

Reading: §3.1

9/8—NP and NP completeness

Reading: §2–2.2

9/10—NP and hardness reductions

Reading: §2.4

9/15—Intermediate problems in NP

Reading: §3.3

9/17—Ladner’s theorem and diagonalization

Reading: §3.3

9/22—Oracles and limitations of relativizing proofs

Reading: §3.4

9/24—coNP and good characterizations I

Reading: §2.6.1, 2.7.4 notes pdf

9/29—coNP and good characterizations II

Reading: §2.6.1, 2.7.4 notes pdf

10/1—Cryptography I: one-time pad, perfect secrecy

Reading: §9.1

10/6—Cryptography II: computational security, one-way functions

Reading: §9.2

10/8—prelim I

10/15—Boolean Circuits I: examples, upper bounds

Reading: §6.1

10/20—Boolean Circuits II: lower bounds

Reading: §6.1

10/22—Boolean Circuits III: Cook–Levin theorem

Reading: §6.1.2

10/27—Randomized Computation I: BPP and polynomial identity testing

Reading: §7.1, §7.2.2

10/29—Randomized Computation II: Error reductions and circuits

Reading: §7.4.1, §7.5.1

11/3—Interactive Proofs I: IP and graph non-isomorphism

Reading: §8.1

11/5—prelim II

11/10—Interactive Proofs II: IP and graph isomorphism

Reading: §8.1, §8.2

11/12—Interactive Proofs III: private vs public coins

Reading: §8.2

11/17—Regular expressions and finite automata

notes 1, notes 2, notes 3, notes 4

11/19—State minimization for finite automata

notes by Trevisan and Williams

11/24—Streaming algorithms and finite automata

notes by Trevisan and Williams

12/1—Hardness of approximation and the PCP Theorem

Reading: §11.1–3