Communication complexity


In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is 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.
The problem is usually stated as follows: two parties each receive a -bit string and. The goal is for Alice to compute the value of a certain function,, that depends on both and, with the least amount of communication between them.
While Alice and Bob can always succeed by having Bob send his whole -bit string to Alice, the idea here is to find clever ways of calculating with fewer than bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob.
This abstract problem with two parties, and its general form with 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 and.

Formal definition

Let where we assume in the typical case that and. Alice holds an -bit string while Bob holds an -bit string . By communicating to each other one bit at a time, Alice and Bob wish 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 problem of computing, denoted as, is then defined to be
As observed above, for any function, we have.
Using the above definition, it is useful to think of the function as a matrix where the rows are indexed by and columns by. The entries of the matrix are. Initially both Alice and Bob have a copy of the entire matrix . 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 matrix position corresponding to 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 position reduces, as this eliminates a set of rows/columns, resulting in a submatrix of.
More formally, a set is called a rectangle if whenever and then. Equivalently, is a combinatorial rectangle if it can be expressed as for some and. Consider the case when bits are already exchanged between the parties. Now, for a particular, let us define a matrix
Then, and it is not hard to show that is a combinatorial rectangle in.

Example: ''EQ''

We consider the case where Alice and Bob try to determine whether or not their input strings are equal. Formally, define the Equality function, denoted, by if. As we demonstrate below, any deterministic communication protocol solving requires bits of communication in the worst case. As a warm-up example, consider the simple case of. The equality function in this case can be represented by the matrix below. The rows represent all the possibilities of, the columns those of.
EQ000001010011100101110111
00010000000
00101000000
01000100000
01100010000
10000001000
10100000100
11000000010
11100000001

In this table, the function only evaluates to 1 when equals . It is also fairly easy to see how communicating a single bit divides someone's possibilities in half. When the first bit of is 1, consider only half of the columns.

Theorem: ''D(EQ) = n''

Proof. Assume that. This means that there exists such that and have the same communication transcript. Since this transcript defines a rectangle, must also be 1. By definition and we know that equality is only true for when. This yields a contradiction.
This technique of proving deterministic communication lower bounds is called the fooling set technique.

Randomized communication complexity

In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of with much less information exchanged? Yao, in his seminal paper
answers this question by defining randomized communication complexity.
A randomized protocol for a function has two-sided error.
A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O additional bits compared to the original.
In the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R yields g when using random string r, then g = f for at least 2/3 of all choices for the string r.
The randomized complexity is simply defined as the number of bits exchanged in such a protocol.
Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.

Example: EQ

Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string. Alice computes and sends this bit to Bob. Then Bob compares b to. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.
Clearly, if, then, so. If x does not equal y, it is still possible that, which would give Bob the wrong answer. How does this happen?
If x and y are not equal, they must differ in some locations:
Where and agree, so those terms affect the dot products equally. We can safely ignore those terms and look only at where and differ. Furthermore, we can swap the bits and without changing whether or not the dot products are equal. This means we can swap bits so that contains only zeros and contains only ones:
Note that and. Now, the question becomes: for some random string, what is the probability that ? Since each is equally likely to be or, this probability is just. Thus, when does not equal,
. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.
This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute. In the next section, it is shown that Alice and Bob can exchange only bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in messages.

Example: GH

For yet another example of randomized communication complexity, we turn to an example known as the gap-Hamming problem. Formally, Alice and Bob both maintain binary messages, and would like to determine if the strings are very similar or if they are not very similar. In particular, they would like to find a communication protocol requiring the transmission of as few bits as possible to compute the following partial Boolean function,
Clearly, they must communicate all their bits if the protocol is to be deterministic, then can we get away with a protocol with fewer bits? It turns out that the answer somewhat surprisingly is no, due to a result of Chakrabarti and Regev in 2012: they show that for random instances, any procedure that is correct at least of the time must send bits worth of communication, which is to say essentially all of them.

Public coins versus private coins

Creating random protocols becomes easier when both parties have access to the same random string, known as a shared string protocol. However, even in cases where the two parties do not share a random string, it is still possible to use private string protocols with only a small communication cost. Any shared string random protocol using any number of random string can be simulated by a private string protocol that uses an extra O bits.
Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.
Consider some random protocol P with a maximum error rate of 0.1. Let be strings of length n, numbered. Given such an, define a new protocol that randomly picks some and then runs P using as the shared random string. It takes O = O bits to communicate the choice of.
Let us define and to be the probabilities that and compute the correct value for the input.
For a fixed, we can use Hoeffding's inequality to get the following equation:
Thus when we don't have fixed:
The last equality above holds because there are different pairs. Since the probability does not equal 1, there is some so that for all :
Since has at most 0.1 error probability, can have at most 0.2 error probability.