LEC # | TOPICS | KEY DATES |
---|---|---|
1 | Introduction | |
2 | Logic | |
3 | Circuits and finite automata | Problem set 1 assigned |
4 | Turing machines | |
5 | Reducibility and Gödel | |
6 | Minds and machines | |
7 | Complexity |
Problem set 1 due Problem set 2 assigned |
8 | Polynomial time | |
9 | P and NP | |
10 | NP-completeness | |
11 | NP-completeness in practice |
Problem set 2 due Problem set 3 assigned |
12 | Space complexity and more | |
13 | Randomness | Problem set 3 due |
14 | Probabilistic complexity classes | |
In-class midterm | ||
15 | Derandomization / cryptography double feature | |
16 | Private-key cryptography | Problem set 4 assigned |
17 | Public-key cryptography | |
18 | Cryptographic protocols | |
19 | Interactive proofs / machine learning | Problem set 4 due |
20 | Probably Approximately Correct (PAC) learning | Problem set 5 assigned |
21 | Learning, Chomsky, RSA, quantum | |
22-23 | Quantum computing | |
24 | Quantum algorithms | Problem set 5 due |