We solve some fundamental problems in the number-on-forehead (NOF) -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 0"> and every players, where is the number of bits on each player's forehead. As a consequence, we obtain the NOF communication class separation . This in particular implies that and . We also show that for every 0"> and every , 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 log players. However, for every 0"> and every log players, the separation (and even the separation) was obtained independently by Gavinsky and Sherstov (2010) using an explicit construction. In this work, for log players, we exhibit an explicit function which has communication complexity for public coin protocols and log for deterministic protocols. This improves the best previously known deterministic lower bound for a function with efficient randomized protocols, which was log log , given by Beigel, Gasarch, and Glenn (2006).

It follows from our existential result that any function that is complete for the class of functions with polylogarithmic nondeterministic -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.