Abstract. We solve some fundamental problems
in the number-on-forehead (NOF) k-party communication model. We show
that there exists a function which has at most logarithmic
communication complexity for randomized protocols with a one-sided
error probability of 1/3 but which has linear communication complexity
for deterministic protocols. The result is true for k = n^O(1) players,
where n is the number of bits on each players' forehead. This separates
the analogues of RP and P in the NOF communication model. We also show
that 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 and we do not
know of any explicit function which allows such separations. However,
for the 3-player case we exhibit an explicit function which has
Omega(log
log n) randomized complexity for private coins but only constant
complexity for public coins.
It follows from our existential result that any function that is
complete for the class of functions with polylogarithmic
nondeterministic k-party 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.