Theory Matters - Visioning/CommunicationComplexity

view · edit · attach · print · history

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

Image Ideas

List ideas for possible images. You can also upload images you've find using a command like this Δ.

Comments

to give feedback on this nugget, just add another bullet to this list.
Summary can be made more accessible to a lay-reader by a slight expansion, eg. "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. Communication complexity studies the amount of communication needed for parties to carry out arbitrary computations on data distributed among them. Moreover, and often surprisingly, even though the model allows the participants unlimited computational resources, it turns out to be intimately related to understanding what can be computed with various forms of limited computational resources." - Salil
Minor comments: "the basic problem" -> "a basic problem", "that natural effort" -> that much effort", "after sufficient understading...exist" ->"after a sufficient understanding...exists" - Salil
I love the Alice/Bob example: it is more catchy than the summary, something that will get non-theory people interested and will draw them in. Can we move it into the summary? --Anupam
Note from designer Elaine Park: It seems to me that the implications of this area are so incredibly diverse and complex, that the most effective way to approach a visual mnemonic is to create as simple a look as possible. Tin cans and a string that can still transmit a stream of data also suggest "what can be computed with various forms of limited computational resources."
suggest changing tagline to "How much information must flow WITHIN a system". "flow in a system" is fine but the picture strongly suggests "flow into a system," which would be wrong, i guess, so "within" helps resolve that ambiguity. - bernard
I like the clean look of the image. Perhaps in the accompanying text, replace "in a system" with "through a system"? Also, it seems that the bottom 1/4 of the title text is obscured by a white box. -- Rocco
The tagline does not give any hint on what we plan to do and why it is important. - Sanjeev
Following Anupam's suggestion, here's a possible alternate 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. - Salil
The rationale paragraph "This model" could be made more accessible (explaining the various application areas a bit more), and could say a bit more about what future/ongoing research on this topic is trying to accomplish. - Salil
Uploaded revised ppt design (title text no longer cut off). - Salil
I like the idea of having some explanatory bullets: (a) Vast generalization of Shannon's information theory. (b) Useful in x, y, z... (suggestions: lowerbounds for linear programs and boolean circuits, algorithms for streaming data, ..)

---Sanjeev

Revised to accomodate some comments (7/25). Avi
Reorganized summary & rationale. - Salil
Uploaded design with new colors (as suggested by Avi). - Salil