Abstract
Distributed computing is a natural application domain for communication complexity: the typical distributed system has multiple participants, each with only a partial view of the global state of the system, and the players must communicate to achieve some shared goal. Communication is often the most important resource, because its cost is usually orders-of-magnitude greater than the cost of local computation.
In this talk we describe how two-party information complexity can be extended to the multi-party setting, and how it has recently been used to obtain strong lower bounds. We point out that several nice properties of the two-party model unfortunately do not carry over to multi-party communication, so new notions are necessary.