Instructors: Omar Fawzi, Pascal Koiran, and Stéphan Thomassé
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