Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola

### 1 Lecture 15, Scribe: Chin Ho Lee

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.

### 2 Number-on-forehead communication complexity

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 .

For context, let us state and prove the upper bound for randomized communication.

**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 .

To prove a lower bound for deterministic protocols, where , we reduce the communication problem to a combinatorial problem.

**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 .

We now state the theorem that gives the lower bound.

**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 .

### References

[BDPW10] Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel. Separating deterministic from randomized multiparty communication complexity. Theory of Computing, 6(1):201–225, 2010.