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