Lectures

(Will be updated as the semester progresses)

8/27 — Introduction

Reading: § 0.1, 1.1.

8/29 — Turing machine I: the computational model

Reading: § 1.1-1.2

9/3 — Turing machine II: Robustness of the model

Reading: § 1.1-1.4

9/5 — Turing machine III: Universal TM, computability, reductions

Reading: § 1.5.1

9/10 — (Deterministic) Time Hierarchy Theorem

Reading: § 3.1

9/12 — NP and NP completeness I: definition, examples

Reading: § 2.1, 2.2

9/17 — NP hardness reductions

Reading: § 2.4

(Guest lecture: Mohit Gurumukhani)

9/19 — The Cook-Levin theorem

Reading: § 2.4, 2.3

(Guest lecture: Yunya Zhao)

9/24 — Ladner's theorem: I

Reading: § 3.4

9/26 — Ladner's theorem: II

Reading: § 3.4

10/1 — Oracles and limits of diagonalization: I

Reading: § 3.5

(Guest lecture: Prof. Bobby Kleinberg)

10/8 — Oracles and limits of diagonalization: II

Reading: § 3.5

10/10 — Space Complexity: Introduction

Reading: § 4.1, 4.2

10/17 — Space Complexity: Savitch's Theorem

Reading: § 4.3

10/22 — Space Complexity: PSPACE-completeness

Reading: § 4.3

10/24 — Boolean Circuits: Introduction

Reading: § 6.1

10/29 — Boolean Circuits: Upper & Lower Bounds

Reading: § 6.3

10/31 — Randomized Computation: Introduction

Reading: § 7.1, 7.2

11/5 — Randomized Computation: Error Reduction

Reading: § 7.4

11/7 — Randomized Computation: Error Reduction (cont'd), BPP in P/poly

Reading: § 7.4, 7.6

11/12 — Interactive Proofs: Introduction

Reading: § 8.1

11/14 — Interactive Proofs: Graph Non-Isomorphism

Reading: § 8.2, 8.3

11/19 — AM protocol for Graph Non-Isomorphism

Reading: § 8.4

11/21 — Zero-Knowledge Proofs

11/26 — Probabilistically Checkable Proofs

Reading: § 18.1, 18.2

12/3, 12/5 — Student Presentations