Communication complexity is an area of complexity theory dedicated to the
study of how much communication is needed in order to evaluate a function
when its input is split among several computationally unbounded players.
The "number-on-forehead" (NOF) and "number-in-hand" (NIH) are natural
extensions of the usual 2-player communication model. In general, k denotes
the number of players, and n denotes the number of bits given to each
player. In the NIH model, the part of the input given to each player is
private to that player.  In contrast, in the NOF model, the part of the
input given to each player is metaphorically placed on that player's
forehead, so that each player sees everybody else's input but its own.

In this work, we solve some fundamental questions about the k-player NOF
communication model.  First, we show that for k at most polynomial in n,
randomized protocols are strictly more powerful than deterministic
protocols. This separates the equivalents of complexity classes P and RP in
the NOF model. Second, we show that for k at most logarithmic in n,
nondeterministic protocols are strictly more powerful than randomized
protocols, thus separating the equivalents of complexity classes RP and NP.

Furthermore, we consider augmenting the usual streaming model of
computation with a stack. We use a reduction from NIH communication
complexity to give lower bounds in this model for the well-known problem of
approximating the frequency moments of a data stream.