Computer Science Dartmouth College

Computer Science 85/185 Lower Bounds in Computer Science Amit Chakrabarti

Fall 2003

Course Description

In this course we shall study things that computers cannot do. In a typical Algorithms course we learn several ingenious techniques to solve problems efficiently. In contrast, in this course we shall learn how to prove that certain problems cannot be solved too efficiently. For example, you probably know that a set of n integers can be sorted using O(n log n) comparisons. We shall now learn how to prove that O(n log n) is the best we can hope to do: in other words, (n log n) is a lower bound on the number of comparisons required to sort.

During the course we shall survey lower bound results from a wide range of areas in Computer Science. Broadly, we shall study decision trees, Boolean circuits, and communication protocols. We shall consider simple looking problems from each of these areas but, as we shall learn, even innocent looking lower bound results can be quite a challenge to prove.

Proving lower bounds requires a puzzle-solving bent of mind rather than extensive knowledge of Algorithms; this course will involve quite different ways of thinking than CS 25. A love of mathematical reasoning always helps, but we will not be using any advanced mathematics itself.

• Sep 25: Please read more about Yao's minimax principle from the book "Randomized Algorithms", by Motwani and Raghavan. The relevant sections are 2.1 and 2.2.
• Oct 6: An error in the remark made after problem 5.2 (homework 1) has been fixed. This does not affect any of the problems.
• Oct 30: If you haven't done so already, please complete the mid-term survey and drop it off in my mailbox.
• Nov 13: We're now into communication complexity. A good textbook which covers this material (and much more) is "Communication Complexity", by Kushilevitz and Nisan. If you want to read something with the definitions spelled out, this is the place to look.

Here is the planned list of topics as of the first day of Fall term classes. Below is information about what we're actually doing in the classes.

Handouts are accessible only from within Dartmouth, for copyright reasons.

Sep 25	Our first lower bound: sorting by comparisons, deterministically. Yao's minimax principle. How to handle randomization. Some lower bounds for selection. Handout 1: A Counting Approach to Lower Bounds for Selection Problems. (Fussenegger and Gabow, JACM 26(2))
Sep 30	Decision trees for Boolean functions. Deterministic decision tree complexity. Other comlexity measures: certificate complexity, sensitivity, block sensitivity, polynomial degree. Connections between these measures. Homework 1 assigned [PS version | PDF version ]. Due Oct 7, at start of class. Handout 2: Important Homework Guidelines: please read carefully! [LaTeX version | PS version]
Oct 2	Randomized decision tree complexity. Approximate degree. Connections between these and previously discussed complexity measures. Stronger results for symmetric functions and monotone functions. Graph properties and the evasiveness conjecture.
Oct 7	Results in support of the evasiveness conjecture. The Rivest-Vuillemin theorem, with proof. The Kahn-Saks-Sturtevant topological approach. Handout 3: A Generalization and Proof of the Aanderaa-Rosenberg Conjecture. (Rivest and Vuillemin, STOC 1975)
Oct 9	Some results that use the topological approach: evasiveness of bipartite graph properties [Yao] and of minor-closed properties [Chakrabarti-Khot-Shi]. New topic: Introduction to algebraic decision and computation trees. Handout 4: Lower Bounds for Algebraic Computation Trees. (Ben-Or, STOC 1983)
Oct 14	No lecture, due to FOCS 2003.
Oct 16	Set recognition problems. Counting connected components. Lower bounds in the linear decision tree model. Ben-Or's theorem: lower bounds in the algebraic computation tree model. Application of the theorem to element distinctness and related problems. Homework 2 assigned [PS version | PDF version ]. Due Oct 30, at start of class.
Oct 21	No lecture, Amit is out of town.
Oct 23	No lecture, Amit is out of town.
Oct 28	Introduction to circuits and circuit complexity. Polynomial time computable implies existence of polynomial sized circuit family. Lower bound for the THRESHOLD-2 function. Introduction to the class AC0.
Oct 30	Håstad's switching lemma. Proof that PARITY is not in AC0. Look at these lecture notes from Dan Spielman's course at MIT for a compact write-up of the proof.
Nov 4	Circuits with modulo gates and the class AC0[m]. Proof that PARITY is not in AC0[3]. See Section 6.4 in the textbook by Du and Ko. Handout 6: Solutions to the first five problems from Homework 2 [PS version | PDF version].
Nov 6	Monotone circuits. The CLIQUEn,k function and the first half of the proof of Razborov's lower bound on its monotone circuit complexity. Positive and negative test graphs. Clique indicators and clean functions.
Nov 11	Continuation and completion of Razborov's proof. The method of approximations. How to estimate the effect of approximation on positive and negative test graphs, including an application of the Erdos-Rado sunflower lemma.
Nov 13	Communication protocols and communication complexity. A nontrivial protocol for median finding. The rectangle property of determinstic protocols. Lower bounds for the equality problem using (a) the rectangle property, (b) the fooling set method, and (c) the rank method. Homework 3 assigned [PS version | PDF version ]. Due Nov 20, at start of class.
Nov 18	Randomized communication complexity. Efficient randomized protocols for the equality problem. Private coin versus public coin. Randomized versus deterministic complexity. Lower bound on randomized complexity using the discrepancy technique. Application to the inner product function. Handout 7: Some brief notes on this material [PS version | PDF version].
Nov 20	Review of information theory. Entropy, mutual information, conditional entropy. Information complexity. Direct sum theorem. Lower bound for the bit lookup problem. Homework 4 assigned [PS version | PDF version ]. Due Dec 2, at start of class.
Nov 25	Randomized lower bound for set disjointess via information complexity. Communication complexity of relations. Lower bounds using the "critical set lemma".
Dec 2	Application of communication complexity to lower bounds in circuit complexity. Final remarks: (a) things we have learnt, (b) things that are out there for you to learn, (c) questions that no one can answer as yet but would like to, (d) some big but perhaps distant goals.