Theory of Computing
-------------------
Title     : Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
Authors   : Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Volume    : 19
Number    : 10
Pages     : 1-44
URL       : https://theoryofcomputing.org/articles/v019a010

Abstract
--------

In a $k$-party communication problem, the $k$ players with inputs
$x_1, x_2, \ldots, x_k$ 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(\eps^{-2}\log(N) \log \log(mM))$ bits of space lower bound for
the fundamental problem of $(1\pm\eps)$-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(\eps^{-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
$\eps\ge 1/\polylog(mM)$ and when $T = 2^{\poly(1/\epsilon)}$,
respectively. It also improves on the prior $\Omega(\eps^{-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(\eps^{-2}\log (mM))$ bit upper bound.

----------------

A preliminary version of this paper, by a subset of the authors,
appeared in the Proceedings of the 46th International Colloquium
on Automata, Languages and Programming, 2019 (ICALP'19).