In this lecture fragment we discuss multiparty communication complexity, especially the problem of separating deterministic and randomized communication, which we connect to a problem in combinatorics.
In number-on-forehead (NOH) communication complexity each party sees all of the input except its own input . For background, it is not known how to prove negative results for parties. We shall focus on the problem of separating deterministic and randomizes communication. For , we know the optimal separation: The equality function requires communication for deterministic protocols, but can be solved using communication if we allow the protocols to use public coins. For , the best known separation between deterministic and randomized protocol is vs [BDPW10]. In the following we give a new proof of this result, for a simpler function: if and only if for .
Claim 1. has randomized communication complexity .
Proof. In the NOH model, computing reduces to -party equality with no additional communication: Alice computes privately, then Alice and Bob check if .
Definition 2. A corner in a group is , where are arbitrary group elements and .
For intuition, consider the case when is Abelian, where one can replace multiplication by addition and a corner becomes for .
Theorem 3. Suppose that every subset with contains a corner. Then the deterministic communication complexity of is .
It is known that when is Abelian, then implies a corner. We shall prove that when , then implies a corner. This in turn implies communication .
Proof. We saw that a number-in-hand (NIH) -bit protocol can be written as a disjoint union of rectangles. Likewise, a number-on-forehead -bit protocol can be written as a disjoint union of cylinder intersections for some :
The proof idea of the above fact is to consider the transcripts of , then one can see that the inputs giving a fixed transcript are a cylinder intersection.
Let be a -bit protocol. Consider the inputs on which accepts. Note that at least fraction of them are accepted by some cylinder intersection . Let . Since the first two elements in the tuple determine the last, we have .
Now suppose contains a corner . Then
This implies , which is a contradiction because and so .