Lecture Topics (tentative)

1/21 — Turing machine I: the computational model

Reading: § 1.1-1.4

1/23 — Turing machine II: more on the computational model

Reading: § 1.1-1.4

1/28 — Turing machine III: computability, reductions

Reading: § 1.5.1

1/30 — Gödel's incompleteness theorem

Reading: § 1.5.2

2/4 — (Deterministic) Time Hierarchy Theorem

Reading: § 3.1

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

Reading: § 2.1, 2.2

2/11 — NP hardness reductions

Reading: § 2.3

2/13 — More reductions, The Cook-Levin theorem

Reading: § 2.4

2/18 — The Cook-Levin theorem (continued)

Reading: § 2.4

2/20 — Ladner's theorem and Diagonalization

Reading: § 3.3

2/25 — February break

2/27 — Oracles and limits of diagonalization I

Reading: § 3.4

3/3 — Oracles and limits of diagonalization II

Reading: § 3.4

3/5 — co-NP and limits to good characterization (Guest lecturer: Éva Tardos)

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

3/10 — PRELIMS 1 (in class)

---

3/12 — Space complexity: introduction, Hierarchy theorem

Reading: § 4.1

---

Extended Spring-break due to Covid-19. All lectures below will be delivered virtually via Zoom.

---

4/7 — Savitch's theorem

Reading: § 4.2.1

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

Reading: § 6.1

4/14 — Boolean circuits II: lower bounds

Reading: § 6.1

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

Reading: § 6.1.2

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

Reading: § 7.1, 7.2

4/23 — Randomized Computation II: More examples

Reading: § 7.2

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

Reading: § 7.4.1, 7.5.1

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

Reading: § 8.1

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

Reading: § 8.1, 8.2

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

Reading: § 8.3

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

Reading: § 9.1