Communication complexity

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 ${\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}$, by ${\displaystyle EQ(x,y)=1}$ if ${\displaystyle x=y}$. As we demonstrate below, any deterministic communication protocol solving ${\displaystyle EQ}$ requires ${\displaystyle n}$ bits of communication in the worst case. As a warm-up example, consider the simple case of ${\displaystyle 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 ${\displaystyle x}$, the columns those of ${\displaystyle y}$.

As you can see, the function only evaluates to 1 when ${\displaystyle x}$ equals ${\displaystyle 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 ${\displaystyle y}$ is 1, you only need to consider half of the columns (where ${\displaystyle y}$ can equal 100, 101, 110, or 111).

Proof. Assume that ${\displaystyle D(EQ)\leq n-1}$. This means that there exists ${\displaystyle x\neq x'}$ such that ${\displaystyle (x,x)}$ and ${\displaystyle (x',x')}$ have the same communication transcript ${\displaystyle h}$. Since this transcript defines a rectangle, ${\displaystyle f(x,x')}$ must also be 1. By definition ${\displaystyle x\neq x'}$ and we know that equality is only true for ${\displaystyle (a,b)}$ when ${\displaystyle a=b}$. This yields a contradiction.

This technique of proving deterministic communication lower bounds is called the fooling set technique.[2]

Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only ${\displaystyle O(\log n)}$ messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string ${\displaystyle z\in \{0,1\}^{n}}$. Alice computes ${\displaystyle z\cdot x}$ and sends this bit (call it b) to Bob. (The ${\displaystyle (\cdot )}$ is the dot product in GF(2).) Then Bob compares b to ${\displaystyle z\cdot y}$. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.

Clearly, if ${\displaystyle x=y}$, then ${\displaystyle z\cdot x=z\cdot y}$, so ${\displaystyle Prob_{z}[Accept]=1}$. If x does not equal y, it is still possible that ${\displaystyle 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:

${\displaystyle {\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 x and y agree, ${\displaystyle 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 x and y differ. Furthermore, we can swap the bits ${\displaystyle x_{i}}$ and ${\displaystyle y_{i}}$ without changing whether or not the dot products are equal. This means we can swap bits so that x contains only zeros and y contains only ones:

${\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}$

Note that ${\displaystyle z'\cdot x'=0}$ and ${\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}$. Now, the question becomes: for some random string ${\displaystyle z'}$, what is the probability that ${\displaystyle \Sigma _{i}z'_{i}=0}$? Since each ${\displaystyle z'_{i}}$ is equally likely to be 0 or 1, this probability is just ${\displaystyle 1/2}$. Thus, when x does not equal y, ${\displaystyle 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 ${\displaystyle EQ(x,y)}$. In the next section, it is shown that Alice and Bob can exchange only ${\displaystyle O(\log n)}$ 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 ${\displaystyle O(\log n)}$ messages.

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, ${\displaystyle x,y\in \{-1,+1\}^{n}}$ 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,

${\displaystyle {\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 ${\displaystyle {\sqrt {n}}-1}$ positions. If another disagreement occurs in any position that is not relayed, then this affects the result of ${\displaystyle {\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 ${\displaystyle 1/3}$ of the time (over random instances ${\displaystyle x,y}$ drawn uniformly at random from ${\displaystyle \{-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 which is correct at least ${\displaystyle 2/3}$ of the time must send ${\displaystyle \Omega (n)}$ bits worth of communication, which is to say essentially all of them.

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 ${\displaystyle R}$ be ${\displaystyle 100n}$ strings of length n, numbered ${\displaystyle r_{1},r_{2},\dots ,r_{100n}}$. Given such an ${\displaystyle R}$, define a new protocol ${\displaystyle P'_{R}}$ which randomly picks some ${\displaystyle r_{i}}$ and then runs P using ${\displaystyle r_{i}}$ as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of ${\displaystyle r_{i}}$.

Let us define ${\displaystyle p(x,y)}$ and ${\displaystyle p'_{R}(x,y)}$ to be the probabilities that ${\displaystyle P}$ and ${\displaystyle P'_{R}}$ compute the correct value for the input ${\displaystyle (x,y)}$.

For a fixed ${\displaystyle (x,y)}$, we can use Hoeffding's inequality to get the following equation:

${\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}$

Thus when we don't have ${\displaystyle (x,y)}$ fixed:

${\displaystyle \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]<\sum _{(x,y)}2^{-2n}=1}$

The last equality above holds because there are ${\displaystyle 2^{2n}}$ different pairs ${\displaystyle (x,y)}$. Since the probability does not equal 1, there is some ${\displaystyle R_{0}}$ so that for all ${\displaystyle (x,y)}$:

${\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}$

Since ${\displaystyle P}$ has at most 0.1 error probability, ${\displaystyle P'_{R_{0}}}$ can have at most 0.2 error probability.

Let's say we additionally allow Alice and Bob to share some resource, for example a pair of entangle particles. Using that ressource, Alice and Bob can correlate their information and thus try to 'collapse' (or 'trivialize') communication complexity in the following sense.

Definition. A resource ${\displaystyle R}$ is said to be "collapsing" if, using that resource ${\displaystyle R}$, only one bit of classical communication is enough for Alice to know the evaluation ${\displaystyle f(x,y)}$ in the worst case scenario for any Boolean function ${\displaystyle f}$.

The surprising fact of a collapse of communication complexity is that the function ${\displaystyle f}$ can have arbitrarily large entry size, but still the number of communication bit is constant to a single one.

Some resources are shown to be non-collapsing, such as quantum correlations [3] or more generally almost-quantum correlations,[4] whereas on the contrary some other resources are shown to collapse randomized communication complexity, such as the PR-box,[5] or some noisy PR-boxes satisfying some conditions.[6][7][8]