Skip to main content
You are not a member of this wiki.
Join now
Dismiss
guest
Help

Sign In
Lower Bounds in Theoretical Computer Science
Home
guest

Help

Sign In
Lower Bounds in Theoretical Computer Science
Wiki Home
Recent Changes
Pages and Files
Members
Favorites
20
All Pages
20
home
Lectures
Add
Add "All Pages"
Done
Lectures
Edit
0
22
…
0
Tags
No tags
Notify
RSS
Backlinks
Source
Print
Export (PDF)
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
)
Javascript Required
You need to enable Javascript in your browser to edit pages.
help on how to format text
Turn off "Getting Started"
Home
...
Loading...
Date
Topic
Readings
Notes
Homework
sorting; Decision trees; Certificates;
Sensitivity and block sensitivity
Complexity measures and decision
tree complexity: A survey
Fernando Krell
and decision tree complexity; Degree
of representing polynomial
Anthi Orfanou
Due on Sep 24
the AKR conjecture and the evasiveness
conjecture; Evasiveness when the number
of variables is a prime power
Revisited, Lecture Notes on
Evasiveness of Graph Properties,
Lecture notes of Jeff Erickson
Yuan Kang
Randomized decision trees; Yao's minimax
principle; An n^{2/3} lower bound for R(f)
Clement Canonne
Due on Oct 22
CC: Computational Complexity: A Modern Approach (draft)