Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 85/185
You Can't Do That
Lower Bounds in Computer Science

Amit Chakrabarti

Spring 2008

Location: Lectures will take place in Sudikoff 245

When: 2A hour: TTh 14:00-16:00 X-hr W 16:15-17:20

What is this course about? Here is one flyer. Here is another.
Maybe those will answer some questions (and leave you with more).

Lecture Plan

I. Decision Trees: Lower Bounds Based on Data Access
1. Mar 25 Yao's minimax lemma. Lower bounds for sorting.
2. Mar 27 Lower bounds for selection. Boolean decision trees, certificate complexity, sensitivity, block sensitivity.
3. Apr 1 Relations between the decision tree complexity and the above measures.
4. Apr 3 Degree and its relation to the above measures.
5. Apr 8 Rivest-Vuillemin theorem: Graph properties and the Evasiveness Conjecture.
6. Apr 10 Randomized complexity. O'Donnell-Saks-Schramm-Servedio theorem. Graph properties redux.
7. Apr 15 Friedgut-Kahn-Wigderson theorem: complexity of graph properties vs threshold probability.
8. Apr 17 Algebraic decision and computation trees
9. Apr 22 Milnor-Thom theorem, Ben-Or's theorem
II. Circuits: Lower Bounds Based on Data Movement
10. Apr 24 Circuits, P/poly, Shannon's theorem, Lower bounds for THR2
11. Apr 29 AC0, Hastad's switching lemma
12. May 1 Circuits with MOD gates, ACC0, Razborov-Smolensky theorem
13. May 6 Monotone circuits, Razborov's great exponential lower bound
14. May 8 Slack
15. May 13 Branching programs, Barrington's theorem
16. May 15 Communication complexity, some basic results
17. May 20 Monotone circuit depth, Karchmer-Wigderson theorem
18. May 22 Slack
19. May 27 Algebraic circuits (time permitting)

Lecture Notes

Thanks to an enthusiastic group of volunteer scribes, we have some excellent lecture notes under development. Please notify Amit if you find any typos or errors in the notes.

Scribing volunteers: Please click here (accessible only from Dartmouth IP addresses) to download the necessary templates for scribing. Simply create a new file, one per lecture, imitate the style of "01comptrees.tex" and include this new file in the master file "lecnotes.tex".

Homework Sets

Homework 1, due Apr 18.

Homework 2, due May 2.

Homework 3, due May 19.

Homework 4, due Jun 2.