## Lifting Lower Bounds, Communication, and Proofs

a survey talk by Toniann Pitassi

#### Oded's comments

The actual content of this survey talk was the *lifting method*
by which lower bounds for weak models of computation
(e.g., decision trees) are translated to lower bounds for
the communication complexity of a related problem,
which in turn are used to derive lower bounds on stronger models
(e.g., via the celebtrated connection to circuit depth
[Karchmer and Wigderson, 1988]).
The translation involves composing the problem for which
lower bounds are known with simple gadgets for the communication
model, obtaining a communication complexity problem.
While algorithms for the weak model yield protocols for the
communication model, we are interested in the opposite direction
of deriving algorithms from protocols (which then allow for obtaining
communication complexity lower bounds). Deriving such algorithms
is an art, which of course includes selecting an adequate starting
problem (for the weak model) and adequate gadgets.

#### The original abstract

Ever since Yao introduced the communication complexity model in 1979,
it has played a pivotal role in our understanding of limitations for
a wide variety of problems in Computer Science. In this talk, I will
present the lifting method, whereby communication lower bounds are obtained
by lifting much simpler lower bounds. I will show how lifting theorems have
been used to solve many open problems in a variety of areas of computer
science, including: circuit complexity, proof complexity, combinatorial
optimization (size of linear programming formulations), cryptography
(linear secret sharing schemes), game theory and privacy. Time permitting,
I will sketch a proof of a unified lifting theorem and discuss some new
applications to pseudodeterminism.

Back to
list of Oded's choices.