[Status: Draft; Subject to change]
For the abbreviation of recommend readings, see the Textbook section in the course page.
| Date | Topic | Reading | HW Release (12:00 EST time) |
HW Deadline (23:59 EST time) |
|---|---|---|---|---|
| Thu 01/23 | Course Overview | [Barak] Chap 0; [slides]; Lens of Computation on the Sciences |
||
| Tue 01/28 | Defining computation: Representing objects and Boolean circuits | [Barak] Chap 2 and Chap 3; [slides] |
||
| Thu 01/30 | Completeness: computing every function | [Barak] Chap 4; [slides] |
HW1 | |
| Tue 02/04 | Code as data, and limitations. | [Barak] Chap 4 and Chap 5; [slides] |
||
| Thu 02/06 | Finite automata. | [Barak] Chap 6; [Sipser] Chapter; [slides] |
||
| Tue 02/11 | Turing machines | [slides] [Barak] Chap 7; Turing's original paper |
HW2 | HW1 Due |
| Thu 02/13 | Equivalent models, RAM models | [slides]; [Barak] Chap 8; An expository of lambda calculus and its deep link with mathematical proof: Proposition as Types |
||
| Tue 02/18 | Uncomputability. | [slides]; [Barak] Chap 9; [MM] Chap 7 |
||
| Thu 02/20 | More uncomputability; Rice's Theorem | [slides]; [Barak] Chap 9; [Sipser] Chap 4.2 |
HW3 | HW2 Due (extended to 02/21, 23:59) |
| Tue 02/25 | Godel's incompleteness | [slides]; [Barak] Chap 11; [Anil Ada] Computational Lens on Godel's Incompleteness Theorems: Part 1, Part 2; An interesting proof of the 2nd Incompleteness Theorem via Kolmogrov Complexity; A nice talk by Terry Tao on machine-assisted proof. |
||
| Thu 02/27 | Midterm Review I | [slides] | ||
| Tue 03/04 | Midterm I | |||
| Thu 03/06 | Efficient computation and P | [slides]; [Barak] Chap 12 and Chap 13.1; [Sipser] Chap 7.1-7.2; [Aaronson] Why Philosophers Should Care About Computational Complexity, section 2 and 3 Two interesting essays on the chasm between polynomial and exponential-time problems, by Barak, and Gamarnik |
HW4 | HW3 Due |
| Tue 03/11 | P, EXP, and the Time hierarchy | [slides]; [Barak] Chap 13 |
||
| Thu 03/13 | P/poly | [slides]; [Barak] Chap 13; [Sipser] Chap 7.4 |
HW5 | HW4 Due |
| Tue 03/18 | Spring break: No class | |||
| Thu 03/20 | Spring break: No class | |||
| Tue 03/25 | Polynomial-time reductions | [slides]; [Barak] Chap 14; [Sipser] Chap 7.4 |
||
| Thu 03/27 | NP and Cook-Levin Theorem | [slides]; [Barak] Chap 15; [Sipser] Chap 7.4 |
HW6 | HW5 Due |
| Tue 04/01 | More reductions | [slides]; [Barak] Chap 15 [Aaronson] Why Philosophers Should Care About Computational Complexity, section 6 |
||
| Thu 04/03 | What if P = NP ? | [slides]; [Barak] Chap 16 [Aaronson] NP-Complete Problems and Physical Reality [Aaronson] P?=NP [Aaronson] Why Philosophers Should Care About Computational Complexity, section 10. [R. Williams] Some Estimated Likelihood for Computational Complexity [V. Williams]On some fine-grained questions in algorithms and complexity. Very readable, highly recommend. |
||
| Tue 04/08 | Midterm Review II | [slides] | ||
| Thu 04/10 | Midterm II | HW6 Due (04/14) | ||
| Tue 04/15 | Probabilistic computation: Probability basics, Randomized approx algorithm for MAX-CUT. | [slides]; [Barak] Chap 18 and Chap 19; [Sipser] Chap 10.2 |
HW7 | |
| Thu 04/17 | Probabilistic computation: BPP, Derandomization | [slides]; [Barak] Chap 20 |
||
| Tue 04/22 | Cryptography I: One-way function, Computational Indistinguishability, Pseudorandomness. | [slides]; [Barak] Chap 21; [Sipser] Chap 10.6 |
||
| Thu 04/24 | Cryptography II: Symmetric-Key Encryption, Public-Key Encryption, Zero-Knowledge Proofs. | [slides]; [Barak] Chap 21 [Aaronson] Why Philosophers Should Care About Computational Complexity, section 9 |
HW8 | HW7 Due |
| Tue 04/29 | Quantum computation I: Basics; Quantum Circuits; BQP. | [slides]; [Barak] Chap 22 [Aaronson] Are Quantum States Exponentially Long Vectors? [Aaronson] Why Philosophers Should Care About Computational Complexity, section 8 |
||
| Thu 05/01 | Quantum computation II: Grover's Algorithm, Shor's Algorithm | [slides]; [Barak] Chap 22 |
||
| Tue 05/06 | Final Review | [slides] | HW8 Due | |
| Fri 05/09 | Final Exam | Time: Fri 05/09, 19:15 - 22:15. Location: NSC 201, |