# CR 08: Lower Bounds Methods

• Prerequisites: No specialized knowedge is required, however basic notions in graph theory, algorithms, complexity theory, linear algebra and discrete probability will certainly help.

• Objective: When designing efficient algorithms for a certain problem P, we try to solve P using as few ressources as possible. In lower bounds, we study the complexity of problems from the complementary point of view: we try to show that P cannot be solved without access to enough ressources (and we try to quantify the amount of ressources that is required to solve P). The ressource under consideration could be computation time or space, amount of communication, number of constraints to express the problem, etc... Ideally, one would like to obtain matching upper and lower bounds for the complexity of a wide variety of problems. In full generality this goal is of course far from achieved, but nevertheless a number of partial results are known. This course will present lower bounds for various models of computation.

• Course outline:

1) Communication Complexity.

Suppose Alice and Bob have inputs x and y and would like to compute F(x,y) for some function F. The communication complexity of F is the number of bits Alice and Bob need to communicate in order to compute F. There are many functions F, such as the disjointness function, for which the communication complexity is well understood. Such functions now play a fundamental role in proving lower bounds on e.g., streaming algorithms and data structures. Communication complexity also offers a clean model to study the relative power of deterministic, randomized and quantum communication.

2) Extended Formulations.

Transforming a discrete problem into an integer program is a natural approach. It allows then to use optimization technique providing that the constraints defining the polytope of admissible solutions are easy to describe. Suprisingly, some easy problems, like minimum weight spanning tree, can be described via an exponential number of constraints. This gap between the structural complexity of the spanning tree polytope, and the simplicity of Kruskal's greedy algorithm to solve this problem can be bridged as follows: The spanning tree polytope is in fact the projection of a polytope in higher dimension (an extended formulation) which admits a polynomial number of facets. In other words, the extended formulation both capture the computational and the structural complexity. The exciting question is then: does every computational problem in P have polynomial extended formulations? Lower bounds are the key here.

3) Boolean and Arithmetic Circuits.

Superpolynomial lower bounds for general boolean circuits seem to be currently out of reach (for instance, they would imply a separation of P from NP). Nevertheless, good lower bounds are known for restricted families of boolean and arithmetic circuits, and in particular for constant-depth circuits. Polynomials play a crucial role in some of these lower bounds. This is to be expected for arithmetic circuits (which are a model for computing polynomials), but is more surprising for boolean circuits. Besides the polynomial method, We will also see some applications of diagonalization.

• Validation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.

• Bibliography:

- Lee and Schraibman, Lower Bounds in Communication Complexity: A Survey
www.research.rutgers.edu/~troyjlee/survey_plain.pdf
- Arora and Barak, Computational Complexity: A modern approach (Ch 12)
- Lecture notes on Communication Complexity (for Algorithm Designers):
http://theory.stanford.edu/~tim/w15/w15.html