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.

• Homework 1, due Jan 16 by 11:59pm.
• Homework 2, due Jan 23 by 11:59pm.
• Homework 3, due Jan 30 by 11:59pm.
• Homework 4, due Feb 6 by 11:59pm.
• Homework 5, due Feb 13 by 11:59pm.
• Homework 6, due Feb 20 by 11:59pm.
• Homework 7, due Mar 7 by 11:59pm.

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.

• S. W. Bent, J. W. John. Finding the median requires 2n comparisons. YC + MJ
  
• D. P. Dobkin, R. J. Lipton. A lower bound of ½n² on linear search programs for the knapsack problem. KM + ZW
  (Requires an understanding of a cited result from this paper: S. Yajima, T. Ibaraki. A lower bound on the number of threshold functions.)
  
• J. von zur Gathen, J. R. Roche. Polynomials with two values.
  
• E. Friedgut, J. Kahn, A. Wigderson. Computing graph properties by randomized subcube partitions. BB + TZ
  
• E. Demenkov, A. S. Kulikov. An elementary proof of a 3n−o(n) lower bound on the circuit complexity of affine dispersers. ZL + BZ
  
• B. Rossman. The average sensitivity of bounded-depth formulas. SB + SS
  (Focus on the proof of Theorem 3.)