Communication complexity (Q1069701)

Suppose that a language \(L\subseteq \{0,1\}^*\) must be recognized by two distant computers. Each computer receives half of the input bits, and the computation proceeds using some protocol for communication between the two computers (obviously, most interesting languages cannot be recognized with any communication). The minimum number of bits that has to be exchanged in order to successfully recognize \(L\cap \{0,1\}^{2n}\), minimized over all partitions of the input bits into two equal parts, and considered as a function of n, is called the communication complexity of L. In this paper we prove several results concerning this complexity measure.