Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 85/185
Lower Bounds in Computer Science

Amit Chakrabarti

Fall 2003

List of Topics

As of Sep 24, 2003 (start of Fall term classes), here is the list of topics we plan to cover. This list may be adjusted based on feedback around half-way through the course.

A⟩ Decision (and other) trees
   0. Lower bounds for sorting (deterministic/randomized)
1. Connection with certificate complexity and sensitivity
2. Connection with polynomial degree and approximate degree
3. Lower bounds for symmetric functions
4. Lower bounds for graph properties
5. Algebraic decision/computation trees
B⟩ Circuits
   6. Non-constructive lower bounds
7. Monotone circuits
8. Circuits with modulo gates
9. Arithmetic circuits
C⟩ Communication Complexity and Applications
   10. The rectangle and rank methods for lower bounds
11. Randomized communication complexity
12. Information complexity
13. Application: Data structures
14. Application: Circuit depth