The notion of communication complexity was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations.
Contents
- Formal definition
- Example EQ
- Theorem D E Q n displaystyle DEQn
- Randomized communication complexity
- Public coins versus private coins
- Quantum communication complexity
- Nondeterministic communication complexity
- Open problems
- Applications
- References
Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with fewer than n bits of communication.
This abstract problem, and its general form with more than two parties, is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required 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 a survey of the field, see the book by Kushilevitz and Nisan.
Formal definition
Let
Using the above definition, it is useful to think of the function f as a matrix A (called the input matrix) where each row of the matrix corresponds to
More formally, a set
Then,
Example: EQ
We consider the case where Alice and Bob try to determine if they both have the same string. That is, we are trying to determine if x is equal to y. It is easy to prove that the equality problem (EQ) will always require you to communicate n bits in the worst case if you want to be absolutely sure x and y are equal. Consider the simple case of x and y being 3 bits. The equality function in this case can be represented by the matrix below. The rows representing all the possibilities of x, the columns those of y.
As you can see, the function only evaluates to 1 when x equals y (i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides your possibilities in half. If you know that the first bit of y is 1, you only need to consider half of the columns (where y can equal 100, 101, 110, or 111).
Theorem: D ( E Q ) = n {displaystyle D(EQ)=n}
Proof. Assume that
Intuitively, for
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
A randomized protocol
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(log n) additional bits compared to the original.
Note that 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(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least half 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 O(log n) messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string
Clearly, if
If x and y are not equal, they must differ in some locations:
Where
Note that
This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute
Public coins versus private coins
It is easier to create random protocols when both parties have access to the same random string (shared string protocol). It is still possible to use these protocols even when the two parties don't share a random string (private string protocol) with 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(log n) 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
Let us define
For a fixed
Thus when we don't have
The last equality above holds because there are
Since
Quantum communication complexity
Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.
At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.
The first one is the qubit-communication model, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber.
In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.
The third model involves access to previously shared entanglement in addition to qubit communication, and is the least explored of the three quantum models.
Nondeterministic communication complexity
In nondeterministic communication complexity, Alice and Bob have access to an oracle. After receiving the oracle's word, the parties communicate to deduce f(x,y). The nondeterministic communication complexity is then the maximum over all pairs (x,y) over the sum of number of bits exchanged and the coding length of the oracle word.
Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the binary logarithm of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.
Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the nonnegative rank of a nonnegative matrix.
Open problems
Considering a 0/1 input matrix
For a randomized protocol, the number of bits exchanged in the worst case, R(f), is conjectured to be polynomially related to the following formula:
Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.
Applications
Lower bounds in communication complexity can be used to prove lower bounds in decision tree complexity, VLSI circuits, data structures, streaming algorithms, space–time tradeoffs for Turing machines and more.