Communication complexity
≈ 19 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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) n -bit string x and y .
The goal is for Alice to compute the value of a certain function, f(x, y) , that depends on both x and y , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole n -bit string to Alice (who then computes the function f ), the idea here is to find clever ways of calculating f with fewer than n 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.…
Evidence and sources
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) n -bit string x and y .
The goal is for Alice to compute the value of a certain function, f(x, y) , that depends on both x and y , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole n -bit string to Alice (who then computes the function f ), the idea here is to find clever ways of calculating f with fewer than n 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.
How it works
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 . Let f: X \times Y \rightarrow Z where we assume in the typical case that X=Y=\{0,1\}^n and Z=\{0,1\} . Alice holds an n -bit string x \in X while Bob holds an n -bit string y \in Y .
By communicating to each other one bit at a time (adopting some communication protocol that is agreed upon in advance), Alice and Bob wish to compute the value of f(x,y) 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 f , denoted as D(f) , is then defined to be D(f) = minimum number of bits exchanged between Alice and Bob in the worst case. As observed above, for any function f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} , we have D(f) \leq n . Using the above definition, it is useful to think of the function f as a matrix A (called the input matrix or communication matrix) where the rows are indexed by x \in X and columns by y \in Y .
The entries of the matrix are A_{x,y}=f(x,y) . Initially both Alice and Bob have a copy of the entire matrix A (assuming the function f 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 x and y . At the start of communication, the number of choices for the matrix position corresponding to the inputs is the size of matrix, i.e. 2^{2n} .
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 A . More formally, a set R \subseteq X \times Y is called a (combinatorial) rectangle if whenever (x_1,y_1) \in R and (x_2,y_2) \in R then (x_1,y_2) \in R . Equivalently, R is a combinatorial rectangle if it can be expressed as R = M \times N for some M \subseteq X and N \subseteq Y . Consider the case when k bits are already exchanged between the parties.
Now, for a particular h \in \{0,1\}^k , let us define a matrix T_{h} = \{ (x, y) : \text{ the }k\text{-bits exchanged on input } (x , y) \text{ is }h\} Then T_{h} \subseteq X \times Y , and it is not hard to show that T_{h} is a combinatorial rectangle in A . 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 EQ : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} , by EQ(x, y) = 1 if x = y .
As we demonstrate below, any deterministic communication protocol solving EQ requires n bits of communication in the worst case. As a warm-up example, consider the simple case of x, y \in \{0, 1\}^3 . The equality function in this case can be represented by the matrix below. The rows represent all the possibilities of x , the columns those of y . In this table, 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 someone's possibilities in half.
When the first bit of y is 1, consider only half of the columns (where y can equal 100, 101, 110, or 111). === Theorem: D(EQ) = n === Proof. Assume that D(EQ) \leq n-1 . This means that there exists x \neq x' such that (x, x) and (x', x') have the same communication transcript h . Since this transcript defines a rectangle, f(x, x') must also be 1. By definition x \neq x' and we know that equality is only true for (a, b) when a = b . This yields a contradiction.
This technique of proving deterministic communication lower bounds is called the fooling set technique. \Pr[R(x,y) = 0] > \frac{2}{3}, \textrm{if }\, f(x,y) = 0 \Pr[R(x,y) = 1] > \frac{2}{3}, \textrm{if }\, f(x,y) = 1 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. 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. Clearly, if x = y , then z \cdot x = z \cdot y , so Prob_z[Accept] = 1 . If x does not equal y, it is still possible that z \cdot x = z \cdot y , which would give Bob the wrong answer. How does this happen?
If x and y are not equal, they must differ in some locations: \begin{cases} x = c_1 c_2 \ldots p \ldots p' \ldots x_n \\ y = c_1 c_2 \ldots q \ldots q' \ldots y_n \\ z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n \end{cases} Where and agree, z_i * x_i = z_i * c_i = z_i * y_i 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 x_i and y_i 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: \begin{cases} x' = 0 0 \ldots 0 \\ y' = 1 1 \ldots 1 \\ z' = z_1 z_2 \ldots z_{n'} \end{cases} Note that z' \cdot x' = 0 and z' \cdot y' = \Sigma_i z'_i . Now, the question becomes: for some random string z' , what is the probability that \Sigma_i z'_i = 0 ? Since each z'_i is equally likely to be or , this probability is just 1/2 . Thus, when does not equal , Prob_z[Accept] = 1/2 . 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 EQ(x,y) . 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. \text{GH}_n(x, y) := \begin{cases} -1 & \langle x, y \rangle \leq \sqrt{n} \\ +1 & \langle x, y \rangle \geq \sqrt{n}. \end{cases} 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 \sqrt{n} - 1 positions.
If another disagreement occurs in any position that is not relayed, then this affects the result of \text{GH}_n(x, y) , and hence would result in an incorrect procedure. A natural question one then asks is, if we're permitted to err 1/3 of the time (over random instances x, y drawn uniformly at random from \{-1, +1\}^n ), 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 2/3 of the time must send \Omega(n) bits worth of communication, which is to say essentially all of them. Consider some random protocol P with a maximum error rate of 0.1. Let R be 100n strings of length n, numbered r_1, r_2, \dots, r_{100n} . Given such an R , define a new protocol P'_R that randomly picks some r_i and then runs P using r_i as the shared random string.
It takes O(log 100n) = O(log n) bits to communicate the choice of r_i . Let us define p(x,y) and p'_R(x,y) to be the probabilities that P and P'_R compute the correct value for the input (x,y) .
Impact
For a fixed (x,y) , we can use Hoeffding's inequality to get the following equation: \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) Thus when we don't have (x,y) fixed: \Pr_R[\exists (x,y):\ |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] The last equality above holds because there are 2^{2n} different pairs (x,y) .
Since the probability does not equal 1, there is some R_0 so that for all (x,y) : |p'_{R_0}(x,y) - p(x,y)| Since P has at most 0.1 error probability, P'_{R_0} can have at most 0.2 error probability. Given a joint distribution \mu on the inputs of both players, the corresponding distributional complexity of a function f is the minimum cost of a deterministic protocol R such that \Pr[f(x,y) = R(x,y)] \ge 2/3 , where the inputs are sampled according to \mu .
Yao's minimax principle (a special case of von Neumann's minimax theorem) states that the randomized communication complexity of a function equals its maximum distributional complexity, where the maximum is taken over all joint distributions of the inputs (not necessarily product distributions!). Yao's principle can be used to prove lower bounds on the randomized communication complexity of a function: design the appropriate joint distribution, and prove a lower bound on the distributional complexity.
Since distributional complexity concerns deterministic protocols, this could be easier than proving a lower bound on randomized protocols directly. As an example, let us consider the disjointness function DISJ: each of the inputs is interpreted as a subset of \{1,\dots,n\} , and DISJ( , )=1 if the two sets are disjoint.
Razborov proved an \Omega(n) lower bound on the randomized communication complexity by considering the following distribution: with probability 3/4, sample two random disjoint sets of size n/4 , and with probability 1/4, sample two random sets of size n/4 with a unique intersection. \operatorname{IC}_\mu(R) = I(\Pi;Y|X) + I(\Pi;X|Y), where denotes conditional mutual information.
The first summand measures the amount of information that Alice learns about Bob's input from the transcript, and the second measures the amount of information that Bob learns about Alice's input. The -error information complexity of a function with respect to a distribution is the infimal information complexity of a protocol for whose error (with respect to ) is at most . Braverman and Rao proved that information equals amortized communication. This means that the cost for solving independent copies of is roughly times the information complexity of .
This is analogous to the well-known interpretation of Shannon entropy as the amortized bit-length required to transmit data from a given information source. Braverman and Rao's proof uses a technique known as "protocol compression", in which an information-efficient protocol is "compressed" into a communication-efficient protocol. The techniques of information complexity enable the computation of the exact (up to first order) communication complexity of set disjointness to be 1.4923\ldots n .
Information complexity techniques have also been used to analyze extended formulations, proving an essentially optimal lower bound on the complexity of algorithms based on linear programming that approximately solve the maximum clique problem. Omri Weinstein's 2015 survey surveys the subject. (f \circ g)(x,y) = f(g(x_{1,1} \cdots x_{1,a}, y_{1,1} \cdots y_{1,b}), \dots, g(x_{n,1} \cdots x_{n,a}, y_{n,1} \cdots y_{n,b})). In words, x is partitioned into n blocks of length a , and y is partitioned into n blocks of length b .
The gadget is applied n times on the blocks, and the outputs are fed into f . Diagrammatically: In this diagram, each of the inputs \mathbf{x}_1,\dots,\mathbf{x}_n is bits long, and each of the inputs \mathbf{y}_1,\dots,\mathbf{y}_n is bits long. A decision tree of depth \Delta for f can be translated to a communication protocol whose cost is \Delta \cdot D(g) : each time the tree queries a bit, the corresponding value of g is computed using an optimal protocol for g .
Raz and McKenzie showed that this is optimal up to a constant factor when g is the so-called "indexing gadget", in which x has length c \log n (for a large enough constant ), y has length n^c , and g(x,y) is the x -th bit of y . The proof of the Raz–McKenzie lifting theorem uses the method of simulation, in which a protocol for the composed function f \circ g is used to generate a decision tree for f . Göös, Pitassi and Watson gave an exposition of the original proof.
Since then, several works have proved similar theorems with different gadgets, such as inner product. The smallest gadget that can be handled is the indexing gadget with c=1+\epsilon . Göös, Pitassi and Watson extended the Raz–McKenzie technique to randomized protocols. A simple modification of the Raz–McKenzie lifting theorem gives a lower bound of \Delta \cdot D(g) on the logarithm of the size of a protocol tree for computing f \circ g , where \Delta is the depth of the optimal decision tree for f .
Garg, Göös, Kamath and Sokolov extended this to the DAG-like setting, and used their result to obtain monotone circuit lower bounds. The same technique has also yielded applications to proof complexity. A different type of lifting is exemplified by Sherstov's pattern matrix method, which gives a lower bound on the quantum communication complexity of f \circ g , where is a modified indexing gadget, in terms of the approximate degree of .
The approximate degree of a Boolean function is the minimal degree of a polynomial that approximates the function on all Boolean points up to an additive error of 1/3. In contrast to the Raz–McKenzie proof, which uses the method of simulation, Sherstov's proof takes a dual witness to the approximate degree of and gives a lower bound on the quantum query complexity of f \circ g using the generalized discrepancy method. The dual witness for the approximate degree of is a lower bound witness for the approximate degree obtained via LP duality.
This dual witness is massaged into other objects constituting data for the generalized discrepancy method. Another example of this approach is the work of Pitassi and Robere, in which an algebraic gap is lifted to a lower bound on Razborov's rank measure. The result is a strongly exponential lower bound on the monotone circuit complexity of an explicit function, obtained via the Karchmer–Wigderson characterization of monotone circuit size in terms of communication complexity.
Considering a 0 or 1 input matrix M_f=[f(x,y)]_{x,y\in \{0,1\}^n} , the minimum number of bits exchanged to compute f deterministically in the worst case, D(f) , is known to be bounded from below by the logarithm of the rank of the matrix M_f . The log rank conjecture proposes that the communication complexity, D(f) , is bounded from above by a constant power of the logarithm of the rank of M_f . Since D(f) is bounded from above and below by polynomials of log rank (M_f) , we can say D(f) is polynomially related to log rank (M_f) .
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), was conjectured to be polynomially related to the following formula: \log \min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3).
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 particular version, called the Log-Approximate-Rank Conjecture, was recently refuted by Chattopadhyay, Mande and Sherif (2019) using a surprisingly simple counter-example. 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.
Dietzfelbinger, M., J. Hromkovic, J., and G. Schnitger, "A comparison of two lower-bound methods for communication complexity", Theoret. Comput. Sci. 168, 1996. 39–51. Raz, Ran. "Circuit and Communication Complexity." In Computational Complexity Theory. Steven Rudich and Avi Wigderson, eds. American Mathematical Society Institute for Advanced Study, 2004. 129–137. A. C. Yao, "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, pp. 209–213, 1979. 14 I. Newman, Private vs.
Common Random Bits in Communication Complexity, Information Processing Letters 39, 1991, pp. 67–71.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375054286 under CC BY-SA 4.0; modifications have been made.