Theory of Computing
-------------------
Title : Separating Deterministic from Randomized Multiparty Communication Complexity
Authors : Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel
Volume : 6
Number : 9
Pages : 201-225
URL : http://www.theoryofcomputing.org/articles/v006a009
Abstract
--------
We solve some fundamental problems in the number-on-forehead (NOF)
k-player communication model. We show that there exists a function
which has at most logarithmic communication complexity for randomized
protocols with one-sided false-positives error probability of 1/3,
but which has linear communication complexity for deterministic
protocols, and in fact, even for the more powerful nondeterministic
protocols. The result holds for every epsilon > 0 and every
k \le 2^{(1-epsilon)n} players, where n is the number of
bits on each player's forehead. As a consequence, we obtain the
NOF communication class separation coRP \not\subset NP. This in
particular implies that P \neq RP and NP \neq coNP.
We also show that for every epsilon > 0 and every k \le n^{1-epsilon},
there exists a function which has constant randomized complexity for
public coin protocols but at least logarithmic complexity for private
coin protocols. No larger gap between private and public coin protocols
is possible.
Our lower bounds are existential; no explicit function is known to
satisfy nontrivial lower bounds for k \ge log n players.
However, for every epsilon > 0 and every k \le (1-epsilon) log n
players, the NP \neq coNP separation (and even the
coNP \not\subset MA separation) was obtained independently by
Gavinsky and Sherstov (2010) using an explicit construction.
In this work, for k < (1/9) log n players, we exhibit an
explicit function which has communication complexity O(1)
for public coin protocols and Omega(log n) for deterministic
protocols. This improves the best previously known deterministic
lower bound for a function with efficient randomized protocols,
which was Omega(log log n) (Beigel, Gasarch, Glenn, 2006).
It follows from our existential result that any function that is complete
for the class of functions with polylogarithmic nondeterministic k-player
communication complexity does not have polylogarithmic deterministic
complexity. We show that the set intersection function, which is
complete in the number-in-hand model, is not complete in the NOF model
under cylindrical reductions.