Lifting theorems in communication complexity and applications

Communication complexity studies the minimal amount of information two parties need to exchange to compute a joint function of their inputs. Results, especially lower bounds in this basic model found applications in many other areas of computer science.

Lifting is a technique for proving lower bounds and separation results in communication complexity. A typical lifting theorem shows how a lower bound on the ``query complexity'' of a function (usually, a far simpler task) can be used to obtain a communication lower bound on a related function. Proofs of lifting theorems require interesting combinations of analytic, information theoretic and combinatorial techniques, and are applicable to a variety of communication models, and beyond.

In the first hour we will give a tutorial on several influential lifting theorems that have been proven in the last 5-10 years, and show how they have directly led to the resolution of many open problems in communication complexity, circuit complexity (including extension complexity) and proof complexity. Time permitting, I will discuss two new lifting theorems in the second hour. The first lifts randomized decision tree complexity to randomized communication complexity (joint work with Mika Goos and Thomas Watson) and the second one lifts Nullstellensatz complexity to a rank measure that captures monotone span programs (joint work with Robert Robere).

No special background will be assumed.