Date

Topic

Readings

Notes

Homework

Sep 3
Course logistics; Comparison based
sorting; Decision trees; Certificates;
Sensitivity and block sensitivity
Chapter 11 of CC
Complexity measures and decision
tree complexity: A survey
Note 1 by
Fernando Krell

Sep 10
Connections between block sensitivity
and decision tree complexity; Degree
of representing polynomial

Note 2 by
Anthi Orfanou
HW 1
Due on Sep 24
Sep 17
Deg vs block sensitivity; Graph properties,
the AKR conjecture and the evasiveness
conjecture; Evasiveness when the number
of variables is a prime power
Gems in Decision Tree Complexity
Revisited, Lecture Notes on
Evasiveness of Graph Properties,
Lecture notes of Jeff Erickson
Note 3 by
Yuan Kang

Sep 24
Linear lower bound for graph properties;
Randomized decision trees; Yao's minimax
principle; An n^{2/3} lower bound for R(f)

Note 4 by
Clement Canonne

Oct 1




Oct 8



HW 2
Due on Oct 22
Oct 15




Oct 22




Oct 29




Nov 5
Election day -- University holiday



Nov 12




Nov 19




Nov 26




Dec 3





CC: Computational Complexity: A Modern Approach (draft)