Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams

In a $k$-party communication problem, the $k$ players with inputs $x_1, x_2, \ldots, x_k$,respectively,wanttoevaluateafunction$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))$bitsofspacelowerboundforthefundamentalproblemof$(1\pm\epsilon)$-approximatingthenumber$|x|_0$ofnon-zeroentriesofan$n$-dimensionalvector$x$after$m$integerupdateseachofmagnitudeatmost$M$,andwithsuccessprobability$\ge 2/3$, in a strict turnstile stream. We additionally prove the matching $\mathrm{\Omega }({ϵ}^{-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 $ϵ\ge 1\mathrm{/}\mathrm{polylog}(mM)$ and when $T = 2^{\operatorname{poly}(1/\epsilon)}$ respectively. It also improves on the prior $\mathrm{\Omega }({ϵ}^{-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({ϵ}^{-2}\log (mM))$ bit upper bound.