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