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 out. | |

11 | 02-21 | Counting | |||

12 | 02-26 | Counting | |||

13 | 02-28 | Interaction | |||

14 | 03-05 | Interaction | ps3 due. ps4 out. | ||

15 | 03-07 | Interation | |||

16 | 03-12 | Cryptography | |||

17 | 03-14 | ||||

03-19 | Spring Break | ||||

03-21 | Spring Break | ||||

18 | 03-26 | Query Complexity | ps4 due. ps5 out. | ||

19 | 03-28 | Communication Complexity | |||

20 | 04-02 | Circuit Complexity | |||

21 | 04-04 | Circuit Complexity | |||

22 | 04-09 | Relativization | ps5 due. ps6 out. | ||

23 | 04-11 | Natural Proofs | |||

24 | 04-16 | Pseudorandomness(?) | |||

25 | 04-18 | Probabilistically Checkable Proofs(?) | |||

26 | 04-23 | Quantum(?) | ps6 due. | ||

27 | 04-25 | Proof Complexity(?) | |||

28 | 04-30 | project presentations | |||

29 | 05-02 | project presentations | project reports due. |