Hardness Escalation in Communication Complexity and Query Complexity

The topic of this workshop is hardness escalation, a growing research area whereby lower bounds and separations in communication complexity are obtained by developing “simulation theorems”. The basic idea of a simulation theorem is to start with a simple ‘one-party’ function and “lift it” to a multi-party setting via function composition; as it turns out in many cases, the communication complexity of the new function can be characterized by the the query complexity of the original function. In query complexity, the objects of study are decision trees, perhaps the simplest, most basic model of computation. A simulation theorem thus essentially shows that the optimal communication protocol for the composed function is essentially the trivial one which mimics the decision tree protocol.

These simulation theorems have introduced new tools into complexity theory, and have led to the resolution of many open problems including: graph theory, combinatorial optimization, circuit complexity and cryptography, proof complexity, game theory, and communication complexity. Moreover the field has led to a revival of query complexity, with new techniques leading to the resolution of some longstanding open problems.

The goal of the workshop is to present a broad introduction to the area as well as highlight the recent developments.


Mika Goos, Robin Kothari, James Lee, Prasad Raghavendra, Robert Robere, Sasha Sherstov, Thomas Watson