Below is the schedule for the class (where italicized descriptions are tentative, and topics with question marks (?) may-or-may-not be covered). This includes the lecture topic, the associated textbook reading, outlines of the lecture (finalized handwritten notes scanned as a .pdf, and occasionally a preliminary .txt file). The psets and pset-schedule are also below.
# | Date | Topic | Reading | Outline | hw |
---|---|---|---|---|---|
1 | 01-17 | Course Introduction | AB Chp. 0 | .txt .pdf | |
2 | 01-22 | Time | AB Chp. 1,3 | .txt .pdf | ps1.tex/.pdf out. |
3 | 01-24 | Nondeterminism | AB Chp. 2 | .txt .pdf | |
4 | 01-29 | NP-Intermediate, Space | AB Chp. 3,4 | ||
5 | 01-31 | Logspace, Circuits | AB Chp. 4,6 | ||
6 | 02-05 | Cook-Levin, Circuits | AB Chp. 5,6 | .txt .pdf | ps1 due. ps2.tex/.pdf out. |
7 | 02-07 | Circuits, Alternation | AB Chp. 6 | .txt .pdf | |
8 | 02-12 | Alternation, Karp-Lipton | AB Chp. 5,6 | .txt .pdf | |
9 | 02-14 | Randomness | AB Chp. 7 | .txt .pdf | |
10 | 02-19 | Randomness | AB Chp. 7 | ps2 due. ps3.tex/.pdf out. | |
11 | 02-21 | Counting | |||
12 | 02-26 | Counting | |||
13 | 02-28 | Interaction | |||
14 | 03-05 | Interaction | ps3 due. ps4.tex/.pdf out. | ||
15 | 03-07 | Interation | |||
16 | 03-12 | Cryptography | AB Chp. 9 | .txt .pdf | |
17 | 03-14 | Cryptography | AB Chp. 9 | .txt .pdf | |
03-19 | Spring Break | ||||
03-21 | Spring Break | ||||
18 | 03-26 | Query Complexity | AB Chp. 12 | .txt .pdf | ps4 due. ps5.tex/.pdf out. |
19 | 03-28 | Communication Complexity | AB Chp. 13 | .txt .pdf | |
20 | 04-02 | Circuit Complexity | AB Chp. 14; pdf | .txt .pdf | |
21 | 04-04 | Circuit Complexity | AB Chp. 14; pdf | .txt .pdf | |
22 | 04-09 | Relativization | AB Chp 3.4 | .txt .pdf | ps5 due. ps6.tex/.pdf out. |
23 | 04-11 | Natural Proofs | AB Chp 23 | .txt .pdf | |
04-16 | Cancelled | ||||
24 | 04-18 | Algebraic Complexity | AB Chp. 16; pdf | .txt .pdf | |
25 | 04-23 | Algebraic Complexity | AB Chp. 16; pdf | .txt .pdf | ps6 due. |
26 | 04-25 | Algebraic Complexity | AB Chp. 16; pdf | .txt .pdf | |
04-30 | project presentations | ||||
05-02 | project presentations | project reports due. |