  In a $k$-party communication problem, the $k$ players with inputs $x_1, x_2,
\ldots, x_k$, respectively, want to evaluate a function $f(x_1, x_2, \ldots,
x_k)$ using as little communication as possible. We consider the
message-passing model, in which the inputs are partitioned in an arbitrary,
possibly worst-case manner, among a smaller number $t$ of players ($t<k$). The
$t$-player communication cost of computing $f$ can only be smaller than the
$k$-player communication cost, since the $t$ players can trivially simulate the
$k$-player protocol. But how much smaller can it be? We study deterministic and
randomized protocols in the one-way model, and provide separations for product
input distributions, which are optimal for low error probability protocols. We
also provide much stronger separations when the input distribution is
non-product.
  A key application of our results is in proving lower bounds for data stream
algorithms. In particular, we give an optimal $\Omega(\epsilon^{-2}\log(N) \log
\log(mM))$ bits of space lower bound for the fundamental problem of
$(1\pm\epsilon)$-approximating the number $\|x\|_0$ of non-zero entries of an
$n$-dimensional vector $x$ after $m$ integer updates each of magnitude at most
$M$, and with success probability $\ge 2/3$, in a strict turnstile stream. We
additionally prove the matching $\Omega(\epsilon^{-2}\log(N) \log \log(T))$
space lower bound for the problem when we have access to a heavy hitters oracle
with threshold $T$. Our results match the best known upper bounds when
$\epsilon\ge 1/\operatorname{polylog}(mM)$ and when $T =
2^{\operatorname{poly}(1/\epsilon)}$ respectively. It also improves on the
prior $\Omega(\epsilon^{-2}\log(mM) )$ lower bound and separates the complexity
of approximating $L_0$ from approximating the $p$-norm $L_p$ for $p$ bounded
away from $0$, since the latter has an $O(\epsilon^{-2}\log (mM))$ bit upper
bound.
