Communication Complexity

In this article we survey the theory of two-party communication complexity. This field of theoretical computer science aims at studying the following, seemingly very simple, scenario. There are two players: Alice, who holds an n-bit string x, and Bob, who holds an n-bit string y. Their goal is to communicate to compute the value of some Boolean function f(x, y), while exchanging a number of bits that is as small as possible. In the first part of this survey we present, mainly by giving examples, some of the results (and techniques) developed as part of this theory. We put an emphasis on proving lower bounds on the amount of communication that must be exchanged in the preceding scenario for certain functions f. In the second part of this survey we exemplify the wide applicability of the results proved in the first part to other areas of computer science. Although it is obvious that there are many applications of the results to problems in which communication is involved (e.g., in distributed systems), we concentrate on applications in which communication does not appear explicitly in the statement of the problems. In particular, we present results regarding the following models of computation: Finite automata Turing machines Decision trees Ordered binary decision diagrams (OBDDs) VLSI chips Networks of threshold gates We provide references to many other issues and applications of communication complexity that are not discussed in this survey.