Abstract: We solve some fundamental problems in the number-on-forehead (NOF) kplayer communication model.We show that there exists a function which has at most logarithmic communication complexity for randomized protocols with one-sided falsepositives 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 k ≤ 2 (1-ε)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 ⊂ NP.This in particular implies that P = RP and NP = coNP.We also show that for every ε > 0 and every k ≤ n 1-ε , 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 ≥ log n players.However, for every ε > 0 and every k ≤ (1ε) • log n players, the NP = coNP separation (and even the coNP ⊂ 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