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)