Lecture Topics (tentative)

2/8 — Turing machine I: the computational model

Reading: § 1.1-1.4

2/11 — Turing machine II: more on the computational model

Reading: § 1.1-1.4

2/16 — Turing machine III: computability, reductions

Reading: § 1.5.1

2/18 — Gödel's incompleteness theorem

Reading: § 1.5.2

2/23 — (Deterministic) Time Hierarchy Theorem

Reading: § 3.1

2/25 — NP and NP completeness I: definition, examples

Reading: § 2.1, 2.2

3/2 — NP hardness reductions

Reading: § 2.4

3/4 — More reductions, The Cook-Levin theorem

Reading: § 2.4, 2.3

3/9 — Wellness day: no class

3/11 — The Cook-Levin theorem (continued)

Reading: § 2.3

3/16 — Ladner's theorem and Diagonalization

Reading: § 3.3

3/18 — Oracles and limits of diagonalization I

Reading: § 3.4

3/23 — Oracles and limits of diagonalization II

Reading: § 3.4

3/25 — co-NP and limits to good characterization

Reading: § 2.6.1, 2.7.4
Additional notes by David Stuerer (from Fall'15 edition of this course): notes

3/30 — Space complexity: introduction, Hierarchy theorem

Reading: § 4.1

4/1 — Savitch's theorem

Reading: § 4.2.1

4/6 — Boolean circuits I: examples, upper bounds

Reading: § 6.1

4/8 — Boolean circuits II: lower bounds

Reading: § 6.1

4/13 — Boolean circuits III: alternate proof of Cook Levin theorem

Reading: § 6.1.2

4/15 — Randomized Computation I: probabistic Turing machines, examples

Reading: § 7.1, 7.2

4/20 — Randomized Computation II: More examples

Reading: § 7.2

4/22 — Randomized computation III: Error reduction and circuits

Reading: § 7.4.1, 7.5.1

4/27 — Interactive proofs I: IP and graph non-isomorphism

Reading: § 8.1

4/29 — Interactive proofs II: IP and graph non-isomorphism

Reading: § 8.1, 8.2

5/4 — Interactive proofs III: public vs private coins

Reading: § 8.3

5/6 — Cryptography I: one-time pad, perfect secrecy

Reading: § 9.1

5/11 — Cryptography II: computational security, one-way functions

Reading: § 9.2

5/13 — Cryptography III: Zero knowledge proofs