Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 49/149
You Can't Do That!
(Lower Bounds in Computer Science)
Amit Chakrabarti

Winter 2017

Where: Sudikoff 115

When: 2A hour: TTh 14:25-16:15, X-hr W 16:35-17:25

Who: Instructor: Amit Chakrabarti, Sudikoff 107, Office hours: Fri 15:00-16:00

What: Computer science is all about using limited resources efficiently. An course in Algorithms course teaches you several techniques to design resource-efficient solutions to computational problems. In this course, we ask the companion question: what can a computer not do when we limit a crucial resource? Equivalently, what lower bounds can we prove on the amount of resources required to solve a problem?

Proving lower bounds is the ultimate challenge of theoretical computer science. Here is a relevant cartoon, which should give you some flavor of the course and leave you intrigued.

Prerequisites: An undergraduate-level course in Algorithms (such as our CS 31)
  or else: A strong mathematics background and permission of the instructor.

Syllabus: The following is a rough outline. Some more detail will be added at the start of term, and an approximate day-by-day plan will be announced shortly after.

  1. Lower Bounds Based on Data Access
    1. Decision trees. Lower bounds for sorting and searching.
    2. Deterministic versus randomized lower bounds.
    3. Boolean functions. Sensitivity and polynomial degree.
    4. Rivest-Vuillemin theorem: Graph properties and the Evasiveness Conjecture.
    5. Randomized complexity of graph properties: OSSS and FKW Theorems.
    6. Algebraic decision and computation trees. Ben-Or's theorem.
  2. Lower Bounds Based on Data Movement
    1. Circuits. Shannon's theorem. Lower bounds for threshold functions.
    2. Hastad's switching lemma. Applications to constant-depth circuits.
    3. Circuits with MOD gates. Razborov-Smolensky theorem.
    4. Monotone circuits. Razborov's amazing exponential lower bound.
    5. Communication protocols. Basic upper and lower bounds.
    6. Monotone circuit depth, Karchmer-Wigderson theorem.
    7. Algebraic circuits (time permitting).

Textbooks: There is no set textbook for this course, but we have some evolving in-house course notes, thanks to the scribing efforts of students from the previous offering of the course. A good fraction of the material we shall study only resides in research papers.

Homework: We will have about 20 homework problems divided into six or seven homework sets. We will mostly stick to the following schedule: homework will be given out on a Tuesday and it will be due by 11:59 pm the following Monday.

Here is a description of the grading principles for these homework sets. Please also note all other applicable policies, including how the honor principle applies to this course.

Class Presentation: In lieu of a final exam, students are required to read up on a paper/topic in the general area of lower bound theory, and give a short, 30-minute presentation on its main ideas. Below is a list of suggested papers for such a presentation.