We study the k-party `number on the forehead' communication complexity of composed functions f \circ \vec{g}, where f:\{0,1\}^n \to \{\pm 1\}, \vec{g} = (g_1,\ldots,g_n), g_i : \{0,1\}^k \to \{0,1\} and for (x_1,\ldots,x_k) \in (\{0,1\}^n)^k, f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots). When \vec{g} = (g,g,\ldots,g) we denote f \circ \vec{g} by ... more >>>

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function f:[N]^3 \to \{0,1\}, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing ... more >>>