  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 it requires sending about $(\log
N)^{1/3}$ many bits. This exponentially improves upon the previously best-known
such separation. At the core of our proof is an extension of a recent result of
the first and third authors on sets of integers without 3-term arithmetic
progressions into a non-arithmetic setting.
