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 (traditionally called Alice and Bob) each receive a (potentially different) formula_1-bit string formula_2 and formula_3. The "goal" is for Alice to compute the value of a certain function, formula_4, that depends on both formula_2 and formula_3, with the least amount of communication between them.
While Alice and Bob can always succeed by having Bob send his whole formula_1-bit string to Alice (who then computes the function formula_8), the idea here is to find clever ways of calculating "formula_8" with fewer than formula_1 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 (called two-party communication complexity), 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 a survey of the field, see the textbook by .
Formal definition.
Let formula_11 where we assume in the typical case that formula_12 and formula_13. Alice holds an formula_1-bit string formula_15 while Bob holds an formula_1-bit string formula_17. By communicating to each other one bit at a time (adopting some "communication protocol" which is agreed upon in advance), Alice and Bob wish to compute the value of formula_18 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 formula_8, denoted as formula_20, is then defined to be
As observed above, for any function formula_22, we have formula_23.
Using the above definition, it is useful to think of the function formula_8 as a matrix formula_25 (called the "input matrix" or "communication matrix") where the rows are indexed by formula_15 and columns by formula_17. The entries of the matrix are formula_28. Initially both Alice and Bob have a copy of the entire matrix formula_25 (assuming the function formula_8 is known to both parties). 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 formula_2 and formula_3. 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. formula_33. 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 formula_25.
More formally, a set formula_35 is called a "(combinatorial) rectangle" if whenever formula_36 and formula_37 then formula_38. Equivalently, formula_39 is a combinatorial rectangle if it can be expressed as formula_40 for some formula_41 and formula_42. Consider the case when formula_43 bits are already exchanged between the parties. Now, for a particular formula_44, let us define a matrix
Then, formula_46, and it is not hard to show that formula_47 is a combinatorial rectangle in formula_25.
Example: formula_49.
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 formula_50, by formula_51 iff formula_52. As we demonstrate below, any deterministic communication protocol solving formula_49 requires formula_1 bits of communication in the worst case. As a warm-up example, consider the simple case of formula_55. The equality function in this case can be represented by the matrix below. The rows represent all the possibilities of formula_2, the columns those of formula_3.
As you can see, the function only evaluates to 1 when formula_2 equals formula_3 (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 formula_3 is 1, you only need to consider half of the columns (where formula_3 can equal 100, 101, 110, or 111).
Theorem: formula_62.
Proof. Assume that formula_63. This means that there exists formula_64 such that formula_65 and formula_66 that have the same communication transcript formula_67. Since this transcript defines a rectangle, formula_68 must also be 1. By definition formula_64 and we know that equality is only true for formula_70 when formula_71. 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 formula_8 with much less information exchanged? Yao, in his seminal paper
answers this question by defining randomized communication complexity.
A randomized protocol formula_39 for a function formula_8 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(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 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 formula_77. Alice computes formula_78 and sends this bit (call it "b") to Bob. (The formula_79 is the dot product in GF(2).) Then Bob compares "b" to formula_80. If they are the same, then Bob accepts, saying "x" equals "y". Otherwise, he rejects.
Clearly, if formula_52, then formula_82, so formula_83. If "x" does not equal "y", it is still possible that formula_82, 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, formula_86 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 formula_87 and formula_88 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 formula_90 and formula_91. Now, the question becomes: for some random string formula_92, what is the probability that formula_93? Since each formula_94 is equally likely to be or , this probability is just formula_95. Thus, when does not equal ,
formula_96. 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 formula_97. 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" (abbreviated "GH"). Formally, Alice and Bob both maintain binary messages, formula_98 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 (this is because, if there is a deterministic, strict subset of indices that Alice and Bob relay to one another, then imagine having a pair of strings that on that set disagree in formula_100 positions. If another disagreement occurs in any position that is not relayed, then this affects the result of formula_101, and hence would result in an incorrect procedure. 
A natural question one then asks is, if we're permitted to err formula_102 of the time (over random instances formula_103 drawn uniformly at random from formula_104), 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 which is correct at least formula_105 of the time must send formula_106 bits worth of communication, which is to say essentially all of them.
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 formula_39 be formula_108 strings of length "n", numbered formula_109. Given such an formula_39, define a new protocol formula_111 which randomly picks some formula_112 and then runs "P" using formula_112 as the shared random string. It takes "O"(log 100"n") = "O"(log "n") bits to communicate the choice of formula_112.
Let us define formula_115 and formula_116 to be the probabilities that formula_117 and formula_111 compute the correct value for the input formula_119.
For a fixed formula_119, we can use Hoeffding's inequality to get the following equation:
Thus when we don't have formula_119 fixed:
The last equality above holds because there are formula_33 different pairs formula_119. Since the probability does not equal 1, there is some formula_126 so that for all formula_119:
Since formula_117 has at most 0.1 error probability, formula_130 can have at most 0.2 error probability.
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 formula_18. The nondeterministic communication complexity is then the maximum over all pairs formula_119 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.
Unbounded-error communication complexity.
In the unbounded-error setting, Alice and Bob have access to a private coin and their own inputs formula_133. In this setting, Alice succeeds if she responds with the correct value of formula_4 with probability strictly greater than 1/2. In other words, if Alice's responses have "any" non-zero correlation to the true value of formula_4, then the protocol is considered valid.
Note that the requirement that the coin is "private" is essential. In particular, if the number of public bits shared between Alice and Bob are not counted against the communication complexity, it is easy to argue that computing any function has formula_136 communication complexity. On the other hand, both models are equivalent if the number of public bits used by Alice and Bob is counted against the protocol's total communication.
Though subtle, lower bounds on this model are extremely strong. More specifically, it is clear that any bound on problems of this class immediately imply equivalent bounds on problems in the deterministic model and the private and public coin models, but such bounds also hold immediately for nondeterministic communication models and quantum communication models.
Forster was the first to prove explicit lower bounds for this class, showing that computing the inner product formula_137 requires at least formula_106 bits of communication, though an earlier result of Alon, Frankl, and Rödl proved that the communication complexity for almost all Boolean functions formula_139 is formula_106.
Open problems.
Considering a 0 or 1 input matrix formula_141, the minimum number of bits exchanged to compute formula_8 deterministically in the worst case, formula_143, is known to be bounded from below by the logarithm of the rank of the matrix formula_144. The log rank conjecture proposes that the communication complexity, formula_143, is bounded from above by a constant power of the logarithm of the rank of formula_144. Since D(f) is bounded from above and below by polynomials of log rankformula_147, we can say D(f) is polynomially related to log rankformula_147. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.
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.