cs579: COMPUTATIONAL COMPLEXITY (SPRING 2018)

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 .pdf
5 01-31 Logspace, Circuits AB Chp. 4,6 .pdf
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.