Communication Complexity


Communication Complexity

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


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


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: