Alice has a number from the set and Bob has a number from the set . They want to evaluate a function of the two numbers they have. The way they communicate with each other is as follows. Alice sends one bit to Bob, then Bob sends one bit to Alice, then Alice sends one bit to Bob and so on. Both of them have unlimited memory and unlimited processing power, so they can do extremely complicated things for deciding what bit they should send in each step. What’s the number of bits they will have to exchange in order to be able to evaluate ?

For example, say the function was just mod 2. In that case, all they would need is an exchange of 1 bit. Alice would send mod 2 and that’s it.

The study of these kinds of questions was started by Yao in the paper titled “Some Complexity Questions Related to Distributive Computing.” However, he does mention an earlier paper that explored similar questions in the case when was any smooth real-valued funtion as opposed to a discrete one. This post is about Yao’s paper. I am going to list down some of the results proved there.

Consider an matrix  that encodes the values of , i.e., . Now consider any subset of rows and any subset of columns. The elements lying in a row of this subset and a column of this subset simultaneously form a rectangle, in the sense that there exists some permutation of the rows and the columns of the matrix for which the elements would lie inside a rectangular box. Let’s call such a rectangle monochromatic if has a constant value for all elements of the rectangle. Let be the minimum number of monochromatic rectangles with which one can cover the whole matrix . Then the first result in the paper says that affects the amount of bits that must be communicated between Alice and Bob if they want to figure out the value of . In particular, the number of bits that must be communicated is .

This is not very difficult to see if you understand what a communication protocol essentially is. In the communication protocol, each player basically gives some information in each step to narrow down the possibilities for what row or column he possesses. For example, before the first bit communicated by Alice, Bob has no idea about the row in which her number lies. But using the one bit of communication, she tells him, say, that her row number is either 1 or 3 or 5. Next, Bob does the same with his columns and so on. Finally, they know the value of the function once the remaining possibility forms a monochromatic rectangle.

This basically suggests a tree like structure where each step corresponds to an edge and the leaves corresspond to monochromatic rectangles. This means that the number of leaves in the tree is at least the number of monochromatic rectangles required to cover the whole matrix. And since at any step, there are a limited number of possible choices, the degree of the tree is bounded by a constant. Finally, since the communication complexity is nothing but the length of the longest path in the tree, the above result follows.

Next, the paper proves that out of all the functions possible between two  numbers in the range , most of them have . This shows that for most functions, the communication complexity is .

What about the upper bound? Suppose we find a decomposition of the matrix into monochromatic rectangles, does this give us a protocol that uses bits of communication? Theorem 2 from the paper says that it does as long as the decomposition satisfies the property that all its rectangles are contiguous. For general decompositions though, all that can be guaranteed is that there exists a protocol that uses bits of communication.

Next, the paper gets into probabilistic models for communication complexity, but I will talk about that later.