Communication Complexity

 

Communication Complexity

How much information must flow within a system to perform a given task?

Summary

“Can we meet next week?” This basic question calls for two parties, say Alice and Bob, to decide if their respective sets of free meeting slots (for the following week) intersect or not. To decide this they have to communicate, and a basic problem is understanding the minimum amount of communication possible. More generally, communication complexity studies the amount of communication needed for parties to carry out arbitrary computations on data distributed among them. This subject is a vast generalization of the field of “information theory” introduced by Shannon, which studies how much communication is needed for parties to simply transmit data to each other. Even though the model allows the participants unlimited computational resources, it surprisingly turns out to be intimately related to understanding what can be computed with various forms of limited computational resources.

Rationale

This model and what it captures are so clean and basic that much effort has gone into understanding it. The diverse set of unexpected applications of this basic model is certainly impressive. It has been used to better understand, among other things, the following areas:

•  Auction theory – resources needed for optimal allocations of goods
•  Boolean complexity – hardware needed for simple computations
•  Linear programming – quality and speed of solving optimization problems
•  VLSI design – how to arrange components and connect them with minimum area
•  Streaming algorithms – handling huge data masses which arrive on-line
•  Quantum computing – harnessing quantum mechanics for computation and communication

Many of these connections are quite subtle, and bring up the need to study natural models for intrinsic reasons — applications are certain to appear, and often only after sufficient understanding of the basic model exists. Better understanding of the basic model and its many variants (having more than two players, allowing them to share information and more) are extremely challenging problems being pursued, with far more applications in store.

Contributors and Credits

Avi Wigderson