Editing Communication complexity (section)

{{Use American English|date=January 2019}}{{Short description|Complexity of sending information in a distributed algorithm}}
In [[theoretical computer science]], '''communication complexity''' studies the amount of communication required to solve a problem when the input to the problem is [[distributed computation|distributed]] among two or more parties. The study of communication complexity was first introduced by [[Andrew Yao]] in 1979, while studying the problem of computation distributed among several machines.<ref name=yao1979>{{Citation
  | last = Yao
  | first = A. C.
  | title = Some Complexity Questions Related to Distributive Computing
  | journal = Proc. Of 11th STOC
  | volume = 14
  | pages = 209–213
  | year = 1979 }}</ref>
The problem is usually stated as follows: two parties (traditionally called [[Alice and Bob]]) each receive a (potentially different) <math>n</math>-[[bit]] string <math>x</math> and <math>y</math>. The goal is for Alice to compute the value of a certain function, <math>f(x, y)</math>, that depends on both <math>x</math> and <math>y</math>, with the least amount of [[communication]] between them.

While Alice and Bob can always succeed by having Bob send his whole <math>n</math>-bit string to Alice (who then computes the [[function (mathematics)|function]] <math>f</math>), the idea here is to find clever ways of calculating ''<math>f</math>'' with fewer than <math>n</math> bits of communication. Note that, unlike in [[computational complexity theory]], communication complexity is not concerned with the [[computational complexity|amount of computation]] performed by Alice or Bob, or the size of the [[computer memory|memory]] used, as we generally assume nothing about the computational power of either Alice or Bob.

This abstract problem with two parties (called two-party communication complexity), and its general form with [[Multiparty communication complexity|more than two parties]], is relevant in many contexts. In [[VLSI]] circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed between the different components during a distributed computation. The problem is also relevant in the study of data structures and in the optimization of computer networks. For surveys of the field, see the textbooks by {{harvtxt|Rao|Yehudayoff|2020}} and {{harvtxt|Kushilevitz|Nisan|2006}}.