# The Complexity of Communication

DevFeed: [The Complexity of Communication](<https://devfeed.tech/articles/the-complexity-of-communication-40369.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/11/10/the-complexity-of-communication/>)

Published: 2014-11-10T09:00:25Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>), [circuit](<https://devfeed.tech/topics/circuit.md>)

Tags: [communication](<https://devfeed.tech/tags/communication.md>), [communication-complexity](<https://devfeed.tech/tags/communication-complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [information-theory](<https://devfeed.tech/tags/information-theory.md>), [log-rank-conjecture](<https://devfeed.tech/tags/log-rank-conjecture.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [matrices](<https://devfeed.tech/tags/matrices.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [theory](<https://devfeed.tech/tags/theory.md>)

## AI overview

This tutorial introduces communication complexity: how much information two parties must exchange to jointly compute a function of separate inputs. It presents the basic two-player model and explains the subject's use in proving lower bounds, including applications to circuit design and streaming algorithms.

## Source excerpt

satellite One of the most interesting questions posed in the last thirty years of computer science is to ask how much "information" must be communicated between two parties in order for them to jointly compute something. One can imagine these two parties living on distant planets, so that the cost of communicating any amount of information is very expensive, but each person has an integral component of the answer that the other does not.