In the table below, ``text'' refers to Michael Sipser's Introduction to the Theory of Computation textbook.
Reading material labeled with ★ is optional.
| DATE | MEETING | READING |
|---|---|---|
| Lecture 1 Sep 12 |
Welcome!
Introduction to the course's topics. |
★Avi's book
§20.2,20.4,20.5 ★Why Philosophers Should Care About Computational Complexity ★NP-complete Problems and Physical Reality |
| Lecture 2 Sep 17 |
Finite Automata and Streaming Protocols Deterministic FA: definition, examples. Nondeterministic FA: definition, DFAs/NFAs equivalence. |
text §1.1-1.2 |
| Lecture 3 Sep 19 |
Regular expressions: definition, examples, equivalence to DFAs. Nonregular languages: proof using the Pumping lemma. |
text §1.3-1.4 |
| Lecture 4 Sep 24 |
Proof of the Pumping lemma. Streaming protocols: setting. Most Frequent Element problem: algorithms. |
text §1.4 Algorithm for MFE |
| Lecture 5 Sep 26 |
Myhill Nerode thm (distinguishably) for space lower bounds. Most Frequent Element problem: space lower bounds. Turing Machines and Computability Theory Deterministic Turing machines: definition, examples. |
★Notes on Myhill-Nerode thm Notes on streaming protocols text §3.1 |
| Lecture 6 Oct 1 |
Deterministic Turing machines: definition, examples. Multi-tape TMs: definition, equivalence to single-tape TMs. Nondeterministic TMs: definition. |
text §3.1-3.3 |
| Lecture 7 Oct 3 |
Nondeterministic TMs: equivalence to deterministic TMs. Decidable and recognizable languages: definitions, examples. | text §3.2,4.1 |
| Lecture 8 Oct 8 |
Diagonalization arguments and undecidable languages (halting). Unrecognizable languages. Reduction: defintions, examples. |
text §4.2,5.1,5.3 |
| Lecture 9 Oct 10 |
Reduction: examples. Rice's thm: statement. |
text §5.1,5.3
|
Lecture 10 Oct 15 |
Rice's thm: proof. Kolmogorov complexity: definition. Undecidability of the compression problem. |
Proof of Rice's thm is answer to Problem 5.28, page 243. Notes on Kolmogorov complexity. ★§6.4 |
Lecture 11 Oct 17 |
Introduction to first order logic. The Soundness thm. Gödel's completeness thm (statement only). |
Notes on Mathematical Logic Video Lecture |
Lecture 12 Oct 22 |
Examples of axiomatic systems. Gödel's first incompleteness thm (proof via halting). |
★More Accurate Proof of Gödel |
Lecture 13 Oct 24 |
Gödel's second incompleteness thm (proof via halting). Church-Turing thm: Provability is undecidable (statement only). Computational Complexity Theory The Extended Church-Turing Thesis. The P complexity class. The time hierarchy thm. The NP complexity class: definition via verifiers. |
text §7.2,7.3,9.1 ★Quantum Supremacy |
FALL BREAK |
| Lecture 14 Nov 5 |
Definition of NP via non-deterministic Turing machines. Polynomial time reductions: definition. NP-complete problems: definition. Cook-Levin thm. |
text §7.3,7.4 |
| Lecture 15 Nov 7 |
Cook-Levin thm (cont'd). NP-complete problems: examples. Ladner's Theorem (statement only). |
text §7.4 |
| Lecture 16 Nov 12 |
More NP-complete problems via reductions. |
text §7.4 |
| Lecture 17 Nov 14 |
Oracle machines, relativizing proofs. Baker-Gill-Solovay thm. The circuits lower bound approch for P vs NP. |
text §9.2,9.3 |
| Lecture 18 Nov 19 |
The PSPACE complexity class: definition. TQBF is PSPACE-complete. PSPACE = NPSPACE. |
text §8.1-8.3 |
| Lecture 19 Nov 21 |
PSPACE and winning strategies in two-players games. The coNP complexity class: definition and examples. PSPACE = NPSPACE = coNPSPACE. Randomness as a computational resource. |
text §8.3,10.2 |
| Lecture 20 Nov 26 |
BPP complexity class: definition, amplification. Relation of BPP to other classes. The P vs BPP problem: examples. Hardness vs randomness and pseudorandom generators (high level). |
text §10.2 Arora-Barak book §7.1,7.2. |
THANKSGIVING BREAK |
| Lecture 21 Dec 3 |
Interactive proofs: the graph-nonisomorphism example IP = PSPACE (statement only). Zero knowledge: the graph-isomorphism example. |
text §10.4. Arora-Barak book §8.3. Note on zero knowledge §3. |
| Lecture 22 Dec 5 |
The PCP (Probabilistically Checkable Proofs) theorem.
Cryptography Cipher encryption. One-time pad encryption. |
Arora-Barak book §18.1. text §10.6. |
| Lecture 23 Dec 10 |
Perfect security. One way function: definition, examples. Existence of OWFs implies P ≠ NP. |
text §10.6. Note on encryption security. |
| Lecture 24 Dec 12 |
Diffie-Hellman public key exchange protocol. Lamport's digital signature scheme. |
Note on Diffie-Hellman. Note on Lamport's signature §2. |