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.
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.