Communication Complexity - Formal Definition

Formal Definition

Let : X Y Z where we assume in the typical case that and . Alice draws an n-bit string X while Bob draws an n-bit string Y. By communicating to each other one bit at a time (adopting some communication protocol), Alice and Bob want to compute the value of such that at least one party knows the value at the end of the communication. At this point the answer can be communicated back so that at the cost of one extra bit, both parties will know the answer. The worst case communication complexity of this communication protocol, denoted as, is then defined to be

minimum number of bits exchanged between Alice and Bob in the worst case

Using the above definition, it is useful to think of the function as a matrix (called the input matrix) where each row of the matrix corresponds to X and each column corresponds to Y. An entry in the input matrix is . Initially both Alice and Bob have a copy of the entire matrix A (assuming the function is known to both). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both and . At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. . Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of A.

More formally, a set R X Y is called a (combinatorial) rectangle if whenever R and R then R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M N where M X and N Y. Consider the case when bits are already exchanged between the parties. Now, for a particular, let us define a matrix

the k-bits exchanged on input is }

Then, X Y, and is a rectangle and a submatrix of A.