Calendar


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