9. Communication Complexity

Let us now move on from query complexity to consider a different model of computation in which randomness plays an important role: communication complexity. In the next few lectures, we broadly follow the presentation of Rao and Yehudayoff (2020)—see the book for the details and much more about communication complexity.

The Model

Communication complexity is concerned with the minimum amount of communication that must be exchanged between various parties to compute a given function on their joint inputs.

We focus on the two-party model of communication. In this model, there are two parties that each obtain part of the input. By convention, the two parties are named Alice and Bob, and we often use \(x\) and \(y\) to denote their respective inputs. The function that Alice and Bob aim to compute is typically a Boolean function \(f \colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}\).

A deterministic communication protocol that Alice and Bob use to compute the value \(f(x,y)\) can be viewed in three different ways:

We will often use \(\pi\) to denote a deterministic communication protocol. The cost of a deterministic protocol \(\pi\) on input \(x\) is the number of bits that are transmitted by the protocol before it terminates. Equivalently, it is the depth of the leaf in the protocol tree reached by the protocol on input \(x\). There is no direct relation between the cost of \(\pi\) and the size of the corresponding rectangle in the matrix representation of a protocol, but a simple argument does show that every protocol that partitions the matrix into \(t\) rectangles must have cost at least \(\log t\) on some input.

A randomized communication protocol with public randomness is a deterministic protocol defined over Alice and Bob’s input and a random string \(r \in \{0,1\}^*\). More precisely: Alice and Bob both see the same random string \(r\) (i.e., the random string is public information) and they can both use it to determine which bit to send next at each step of the procedure. We write \(\pi_r\) to denote the protocol when the random string is set to \(r\). The cost and error parameters of randomized communication protocols are defined using the cost of deterministic protocols as described in Lecture 2.

Throughout this and the next few lectures, we use \(\mathrm{R}(f)\) to denote the bounded-error randomized communication complexity of the function \(f\).

Upper Bounds

Let’s familiarize ourselves with the communication complexity model by working through a few examples.

Equality

We have already seen one example in the very first lecture: the equality function \(\mathsf{EQ}_n \colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}\) that takes the value \(1\) on all inputs \((x,y)\) for which \(x = y\) and \(0\) otherwise.

Theorem. \(\mathrm{R}(\mathsf{EQ}_n) = O(1)\).

We have seen that a valid protocol for this function involves Alice and Bob exchanging the inner products \(\left< x, r \right>\) and \(\left< y, r \right>\) of their respective inputs with the random string \(r \in \{0,1\}^n\).

Another way to view the same protocol is that Alice and Bob treat the random string \(r \in \{0,1\}^n\) as a mask \(S \subseteq [n]\) that determines which bits of their inputs they should consider and which ones they should ignore. Let \(x_S\) and \(y_S\) denote Alice and Bob’s inputs, respectively, when they are restricted to the indices in \(S\). Then Alice and Bob simply exchange the parity of their masked inputs \(x_S\) and \(y_S\).

Greater-Than

A natural variant of the equality function is the greater-than function \(\mathsf{GT}_n \colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}\) where \(\mathsf{GT}_n(x,y)\) takes the value 1 if and only if the string \(x\) is the binary encoding of a natural number that is strictly greater than the number encoded by \(y\).

The greater-than function also has low communication complexity.

Theorem. \(\mathrm{R}(\mathsf{GT}_n) = O(\log n \log \log n)\).

Proof. We can obtain a protocol for \(\mathsf{GT}_n\) by using the protocol for equality as a subroutine. As a first step, we can use the protocol to determine if \(x = y\); if so, the output value is \(0\). But more interestingly, we can then have Alice and Bob run the protocol for equality on their first \(n/2\) bits each. If the strings \(x_{[n/2]}\) and \(y_{[n/2]}\) are equal, then we can ignore them and continue recursively on the last \(n/2\) bits of both inputs. Otherwise, the last \(n/2\) bits of each inputs don’t matter; we can continue recursively on the first half of Alice and Bob’s inputs. Continuing in this way, if each call to equality returns the correct answer, we reach the smallest index \(i \in [n]\) for which \(x_i \neq y_i\); by exchaning this bit, Alice and Bob obtain the value of \(\mathsf{GT}_n(x,y)\).

The one catch about the argument above is the assumption that every call to the procedure that computes equality returns the correct value. In general, this is not true: every call errs with constant probability. However, with success amplification we can can drive down the error probability to less than \(1/10\log n\), say, and apply the union bound to argue that except with probability at most \(1/10\) all calls to the equality subroutine return the correct value.

The recursion calls equality subroutines at \(\lceil \log n \rceil\) levels, and the success amplification can be accomplished with an additional \(O(\log \log n)\) multiplicative factor overhead, giving the bound claimed in the theorem.

We can do even better than the argument above: \(\mathrm{R}(\mathsf{GT}_n) = O(\log n)\). And this bound is tight: unlike for equality, there is no constant-communication protocol that computes this function with bounded error.

k-Disjointness

Another fundamental function in the study of communication complexity is the disjointness function, in which we interpret \(x\) and \(y\) as the indicator functions for sets \(S, T \subseteq [n]\). The function returns \(1\) on an input \((x,y)\) corresponding to the sets \((S,T)\) if and only if \(S \cap T = \emptyset\). We can also define the function as

\[\mathsf{Disj}_n(x,y) = \mathbf{1}[ \sum_{i=1}^n x_iy_i \ge 1].\]

The \(k\)-disjointness function is the partial function \(k\mathsf{Disj}_n \colon X \times Y \to \{0,1\}\) obtained by restricting the disjointness function to inputs that have Hamming weight exactly \(k\). In other words, for this function Alice and Bob have the promise that both of their corresponding sets have cardinality \(|S| = |T| = k\) and they again want to determine whether \(S \cap T = \emptyset\).

By making full use of the idea of treating the random string as a possible mask on the inputs, Johan Håstad and Avi Wigderson (2007) obtained a surprisingly efficient randomized communication protocol for the \(k\)-disjointness function.

Theorem. \(\mathrm{R}( k\mathsf{Disj}_n ) = O(k).\)

Proof. Let us denote Alice and Bob’s inputs as the sets \(S, T \subseteq [n]\). Partition the random string \(r \in \{0,1\}^*\) into a sequence of strings \(r_1,r_2,r_3,\ldots \subseteq \{0,1\}^n\) of length \(n\) each. Alice can find the smallest index \(i\) for which the set \(R_i = \{ j \in [n] : r_j = 1\}\) satisfies \(S \subseteq R_i\). Bob updates his set to be \(T' = T \cap R_i\). Then Bob sends the smallest index \(i' > i\) for which \(T' \subseteq R_{i'}\), and Alice updates her set to be \(S' = S \cap R_{i'}\). Alice and Bob then repeat this process iteratively, continuing to shrink their sets in each round. If either Alice or Bob ends up with an empty set, the protocol ends and outputs 1. Otherwise, if \(c \log k\) rounds have been completed for a large enough constant \(c\) and both players still have a non-empty set, the protocol ends with the value 0.

Let’s examine the correctness of the protocol first. When \(S \cap T \neq \emptyset\), then there is some index \(j \in S \cap T\) that is never eliminated, so the protocol always correctly outputs 0. Conversely, when \(S \cap T = \emptyset\), we can use standard Chernoff-Hoeffding bounds to show that with high probability, a constant fraction of the remaining elements in each set is removed in each round. Therefore, with high probability (that depends on the choice of the constant \(c\)), the algorithm correctly outputs 1.

It remains to bound the cost of this protocol. Note that the probability that a given random string \(r_i\) satisfies the condition that \(S \subseteq R_i\) is exactly \(2^{-|S|}\): each of the \(|S|\) coordinates in \(S\) is included in \(R_i\) with probability \(\frac12\) and all those events are independent. So the probability that none of the first \(2^{2k}\) random strings satisfy the first condition is at most \((1-2^{-k})^{2^{2k}} \le e^{-2^k}\). This means that with high probability Alice’s first message requires at most \(2k\) bits.

And with a naive argument, we could show that the total communication between Alice and Bob is therefore \(O(k \log k)\), since there are \(k\) rounds in the procedure. But we can eliminate the logarithmic factor by noting that the sets get reduced by a constant factor with high probability at each round. This means that with a more careful analysis, we see that the total communication of the protocol forms a geometric series and is thus bounded by \(O(k)\).

The bound is tight, as we will see in later lectures by showing that the general disjointness function has communication complexity \(\Omega(n)\).

Inner Product

One more example: the inner product function \(\mathsf{IP}_n \colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}\) defined by

\[\mathsf{IP}_n(x,y) = x_1y_1 \oplus x_2 y_2 \oplus \cdots \oplus x_n y_n.\]

Can you find a randomized communication protocol that computes this function with \(o(n)\) bits of communication?

We’ll return to this question during the next lecture.