Carnegie Mellon University<EMAIL_ADDRESS>of Computing
Technology, Chinese Academy of Sciences, Beijing, China
Conflux, Beijing<EMAIL_ADDRESS>David P. Woodruff and Guang
Yang[100]Theory of computation Streaming models [100]Theory of computation
Complexity classes [100]Theory of computation Lower bounds and information
complexity

###### Acknowledgements.

We would like to thank Yuval Ishai and Eyal Kushilevitz for initiating the
problem of separating worst-case partition communication complexity from
streaming complexity, which was our starting point. We also thank the ICALP
referees for very helpful comments which helped us revise our initial
submission.

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

David P. Woodruff  Guang Yang

###### Abstract

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(\varepsilon^{-2}\log(N)\log\log(mM))$ bits of space lower bound for
the fundamental problem of $(1\pm\varepsilon)$-approximating the number
$\|x\|_{0}$ of non-zero entries of an $n$-dimensional vector $x$ after $m$
updates each of magnitude $M$, and with success probability $\geq 2/3$, in a
strict turnstile stream. Our result matches the best known upper bound when
$\varepsilon\geq 1/\mathsf{polylog}(mM)$. It also improves on the prior
$\Omega(\varepsilon^{-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(\varepsilon^{-2}\log(mM))$ bit upper
bound.

###### keywords:

Communication complexity, multi-player communication, one-way communication,
streaming complexity

###### category:

##  1 Introduction

Consider a $k$-party communication problem, in which the players have inputs
$x_{1},x_{2},\ldots,x_{k}$ respectively, and want to compute a function
$f(x_{1},x_{2},\ldots,x_{k})$ of their inputs 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. That is, we partition ${\left\\{{1,2,\dots,k}\right\\}}$ into
$t$ subsets $S_{1},S_{2},\ldots,S_{t}$ such that
$\cup_{i=1}^{t}S_{i}={\left\\{{1,2,\dots,k}\right\\}}$ and $S_{i}\cap
S_{j}=\emptyset$ for every $1\leq i<j\leq t$, and let the $i$-th player
$P_{i}$ hold the sequence of inputs
$y_{i}:=\left(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{|S_{i}|}}\right)$. We are still
interested in computing the original function $f$. The total communication
required must be smaller than in the original $k$-player setting, since the
$t$ players can simulate the protocol involving the original $k$ players. A
natural question is: how much smaller can the communication be?

There are many communication models that are possible, but our main motivation
for looking at this question comes from applications to data streams, see
below, and so we are primarily interested in the one-way number-in-hand model.
In this model, each of the $t$ players can only see its own input. The first
player composes a message $m_{1}$ based on its input $y_{1}$ and sends $m_{1}$
to the second player. The second player takes $m_{1}$ and its input $y_{2}$ to
compute a message $m_{2}$ for the third player, and so on. The $t$-th (also
the last) player, upon receiving the message $m_{t-1}$ from the $(t-1)$-st
player, computes the output of the protocol based on $m_{t-1}$ and its own
input $y_{t}$. We sometimes abuse notation and refer to the output as $m_{t}$.
The total communication cost is the maximum of $\sum_{i=1}^{t}|m_{i}|$, where
$|m_{i}|$ denotes the length of the $i$-th message and the maximum is taken
over all possible inputs $y_{1},\ldots,y_{t}$ (which is a partition of
${\left\\{{x_{1},\ldots,x_{k}}\right\\}}$) and all random coin tosses of the
players. For streaming applications we are especially interested in
$\max_{i\in{\left\\{{1,\ldots,t}\right\\}}}|m_{i}|$.

To explain the connection to data streams, almost all known lower bound
arguments on the memory required of a data stream algorithm are proven via
communication complexity, or at least can be reformulated using communication
complexity. The basic idea is to partition the elements of an input stream
contiguously, consisting of say $k$ elements, into a possibly smaller number
$t$ of players. Then one argues that if there is a data stream algorithm
solving the problem, then the communication problem can be solved by passing
the memory contents as messages from player to player. Note that this
naturally gives rise to the one-way number-in-hand model. Since the total
communication cost is $t\cdot S$, where $S$ is the size of the memory of the
streaming algorithm, if the randomized $t$-player communication complexity of
the function $f$ is $CC_{t}$, we must have $S\geq CC_{t}/t$. Many lower bounds
in data streams are proven already with two players. However, it is known that
for some functions more players are needed to obtain stronger lower bounds,
such as for estimating the frequency moments in insertion only streams (see,
e.g., [3, 20] and references therein).

One cannot help but ask how powerful is communication complexity for proving
data stream lower bounds? Another natural question is: for a given function
$f$, which number $t$ of players should one partition the stream into? Yet
another question is regarding the input distribution – should it be a product
distribution for which the inputs to the players are chosen independently, or
should the inputs be drawn from a non-product distribution to obtain the best
space lower bounds? Since we are interested in the limits of using $t$ players
for establishing lower bounds for data stream algorithms, we allow the
original $k$ inputs (which correspond to the $k$ elements in a stream) to be
partitioned in the worst possible way for a $t$-player communication protocol,
as this will give the strongest possible lower bound.

###  1.1 Our Results

In this paper we study these communication questions and their connections to
data streams.

We first make the simple observation that for non-product input distributions,
the communication complexity can be arbitrarily smaller if we partition the
$k$ inputs into $t<k$ players. Indeed, consider the $k$-player set
disjointness problem in which the $i$-th player, $1\leq i\leq k$, has a set
$S_{i}\subseteq[n]$, where for notational simplicity we define
$[n]:={\left\\{{1,2,\dots,n}\right\\}}$ for $n\in\mathbb{N}$. The input
distribution satisfies the promise that either (1) $S_{i}\cap S_{j}=\emptyset$
for every $1\leq i<j\leq k$, or (2) there is a unique item $a\in[n]$ such that
$a\in S_{i}$ for all $i\in[k]$, and for any other $a^{\prime}\neq a$, there is
at most one $i\in[k]$ for which $a^{\prime}\in S_{i}$. It is well-known that
the randomized communication complexity of this problem is
${\Omega\left({n/k}\right)}$ [3, 8, 10], and that the bound holds even for
multiple rounds of communication and players share a common blackboard.
However, if we look at $t<k$ players and an arbitrary, even if the worst-case
mapping of the input sets $S_{1},\ldots,S_{k}$ to the $t$ players, then by the
pigeonhole principle there exists a player who gets two input sets
$S_{i},S_{j}$ with $i\neq j$. Now this player can locally determine the output
of the function by checking if $S_{i}\cap S_{j}=\emptyset$. Thus with $t<k$
players the problem is solvable using ${{O}\left({1}\right)}$ bits per player.
This simple argument shows that for non-product distributions, there can be an
arbitrarily large gap between the $k$-player and the $t$-player worst-case-
partitioned randomized communication complexities. Note that this example
applies to a symmetric problem, meaning that the $k$-player set disjointness
problem is invariant under any one-to-one assignment of $x_{1},\ldots,x_{k}$
to the $k$ players.

Perhaps surprisingly, and this is one of the main messages of our work: for
symmetric functions and product input distributions, we show that for any
$t<k$, for deterministic one-way communication complexity or randomized one-
way communication complexity with error probability $1/\mathsf{poly}(k)$,
there is no gap in maximum message length between the $k$-player and
$t$-player communication complexities. That is, the gap is at most a
multiplicative ${{O}\left({1}\right)}$ factor in message length and $O(k)$ in
total communication. Further, this gap is tight, as there are problems for
which the input distribution is a product distribution, and the $t$-player
communication with $1/\mathsf{poly}(k)$ error probability is ${{O}\left({\log
k}\right)}$ for constant $t={{O}\left({1}\right)}$, while the $k$-player
communication with $1/\mathsf{poly}(k)$ error probability is
${\Omega\left({k\log k}\right)}$. Thus, the answer for product input
distributions is significantly different than what we saw for non-product
distributions, even for symmetric functions.

We also show that for protocols with constant error and under product input
distributions, the gap is at most a multiplicative $O(\log k)$ factor in
message length and $O(k\log k)$ in total communication. Further, we show that
there exists a symmetric function and input distribution which is product on
any $k-1$ out of $k$ inputs, for which this gap is best possible. We leave
open the question of the existence of a symmetric function and product input
distribution (on all $k$ inputs rather than $k-1$ out of $k$) which realizes
this gap for constant error protocols.

One takeaway message from our results is that when showing space lower bounds
for data stream algorithms computing symmetric functions on product
distributions, by looking at $2$-player communication complexity (which is by
far the most common communication setup), there is only an $O(1)$ factor loss
for error probability $1/\mathsf{poly}(k)$ protocols, and an ${{O}\left({\log
k}\right)}$ factor loss for constant error protocols. However, for non-product
distributions, which are often needed to show hardness of approximation in
data streams (such as for the frequency moments [3]), one may need to use as
many as $k$ players in order to obtain a non-trivial lower bound from
communication complexity.

####  1.1.1 Data Stream Lower Bounds:

As a key application of our lower bound techniques, we provide a space lower
bound for $(1\pm\varepsilon)$-approximating the _Hamming norm_ in the strict
turnstile model. This problem, which is also known as the _$L_{0}$ norm
estimation_ and denoted by $\textsc{T}_{\varepsilon}$, requires estimating
${\left\|{\mathbf{x}}\right\|}_{0}:=|{\left\\{{i\;|\;x_{i}\neq 0}\right\\}}|$
of a vector $\mathbf{x}=(x_{1},\ldots,x_{N})$ and outputting an estimate
$\widetilde{F}$ for which
$(1-\varepsilon){\left\|{\mathbf{x}}\right\|}_{0}\leq\widetilde{F}\leq(1+\varepsilon){\left\|{\mathbf{x}}\right\|}_{0}$
with constant probability. The vector $\mathbf{x}$ is initialized to all zeros
and undergoes a sequence of $m$ updates each of the form
$(i,v)\in[N]\times[\pm M]$, where $[\pm M]:={\left\\{{0,\pm 1,\dots,\pm
M}\right\\}}$ and each update $(i,v)$ causes $x_{i}\leftarrow x_{i}+v$. In the
strict turnstile model $x_{i}\geq 0$ holds for all $i$ and at all points in
the stream. We obtain an
${\Omega\left({\varepsilon^{-2}\log(N)\log\log(mM)}\right)}$ bits of space
lower bound for $(1\pm\varepsilon)$-approximating the Hamming norm. This lower
bound matches the best known upper bound
${{O}\left({\varepsilon^{-2}\log(N)\left(\log(1/\varepsilon)+\log\log(mM)\right)}\right)}$
[13] for any $\varepsilon\geq 1/\mathsf{polylog}(mM)$. Note that
$\varepsilon\geq 1/\mathsf{polylog}(mM)$ is required in order to obtain
polylogarithmic space, and so is the most common setting of parameters.
Perhaps surprisingly, there is an upper bound of
${{O}\left({\varepsilon^{-2}\log(mM)}\right)}$ bits of space for
$(1\pm\varepsilon)$-approximating $L_{p}$ for $p>0$ [12] (improving an earlier
${{O}\left({\log^{2}N}\right)}$ bound of [9]; see also a time-efficient
version in [11]), and thus we provide a strict separation in the complexities
for $p=0$ and $p>0$. The Hamming norm has many applications, as it corresponds
to estimating the number of distinct values, and can be used to estimate set
union and intersection sizes (see [7] where it was introduced).

###  1.2 Technical Overview

We first illustrate the idea behind showing there is no gap between $k$-player
and $2$-player deterministic one-round communication complexity. The first
player $P_{1}$ of the $k$-player protocol pretends to be Alice, the first
player of the $2$-player protocol, to create the message $m_{1}$ as Alice
would do and sends it to the second player $P_{2}$ of the $k$-player protocol.
Having received this message $m_{1}$, $P_{2}$ enumerates over all possible
inputs of $P_{1}$ until finding one which would cause $P_{1}$ to send $m_{1}$.
Since the protocol is deterministic and it evaluates a function defined on a
product domain, meaning that it is a total function on a domain of the form
$S_{1}\times S_{2}\times\cdots\times S_{k}$, the function value must be the
same as long as $P_{1}$’s input results in the same message $m_{1}$ to be
sent. So $P_{2}$ can arbitrarily pick one of those inputs as his guess for
$P_{1}$. Now $P_{2}$ has a guess $x$ for $P_{1}$’s input together with his own
input $y$, and $P_{2}$ can simulate Alice in the $2$-player protocol. This is
feasible because the $2$-player protocol works under any partitioning of the
inputs. Then $P_{2}$ sends to the third player $P_{3}$ the message that Alice
would send to Bob in the $2$-player protocol, given that Alice had input
$(x,y)$. In case when every player $P_{i}$ cannot figure out how many input
items have been processed from his own input and the received message
$m_{i-1}$, which is important for his simulation of the $2$-player protocol,
an additional logarithmic-many-bits index carrying this piece of information
should be passed together with the simulated messages. In this way, the entire
$k$-player protocol can be simulated and the per player communication equals
to the communication of the $2$-player protocol between Alice and Bob,
sometimes plus the additional logarithmic many bits for the index. Moreover,
both protocols are deterministic.

For the randomized case with a product input distribution, we first consider
$2$-player protocols with error probability $1/\mathsf{poly}(k)$. We would
like to run the same simulation as for deterministic protocols, except now it
is unclear how the second player $P_{2}$ can reconstruct a valid input $x$ for
the first player $P_{1}$ from the first message $m$. A natural thing would be
for $P_{2}$ to choose the input $x=x_{m}$ to $P_{1}$ for which the probability
of sending $m$, given that $P_{1}$’s input is $x_{m}$, is greatest. This is
not correct though, since the overall probability of $P_{1}$ holding $x_{m}$
and sending $m$ may be less than the $1/\mathsf{poly}(k)$ error bound and the
protocol could afford to be always wrong on such a combination of $x_{m}$ and
$m$. Thus we need some balancing between two probabilities: i) the first
player $P_{1}$ sends $m$ on input $x$; and ii) the protocol output is correct
given that $P_{1}$ has input $x$ and sends $m$.

The above naturally suggests that we should impose an input product
distribution $\mu$. Then it must be that for a good fraction of $x$, weighted
according to $\mu$, the $k$-player protocol is correct when the first player
has input $x$ and sends message $m$. Thus we can sample $x$ from the
conditional distribution on $\mu$ given that message $m$ is sent. Here, for
correctness, it is crucial that $\mu$ is a product distribution; this ensures
for most settings of remaining player’s inputs (weighted according to $\mu$),
for most choices of $x$ (weighted according to $\mu$) giving rise to $m$, the
function evaluated on the inputs is the same, and $x$ can be sampled
independently of remaining inputs. Once we have sampled $x$, and given that
the second player has private input $y$ in the $k$-player protocol, we can
then have the second player pretend to be Alice of a randomized $2$-player
protocol with input $(x,y)$, similar to the deterministic case. Ultimately, we
will show that under distribution $\mu$ we obtain a protocol with total
communication at most ${{O}\left({k}\right)}$ times that of the $2$-player
protocol with error probability $1/\mathsf{poly}(k)$ (and an
${{O}\left({1}\right)}$ multiplicative blowup in maximum message length, times
that of the $2$-player protocol), where the factor $k$ comes from the number
of invocations of the $2$-player protocol.

We illustrate the optimality of the randomized reduction above by looking at
the Sum-Equal problem studied by Viola [19]: in this problem each of $k$
players holds an input $x_{i}\mod p$, where $p={\Theta\left({k^{1/4}}\right)}$
is a prime, and they wish to determine whether $\sum_{i}x_{i}=0$ or $1\mod p$.
Viola shows this problem has randomized communication complexity
${\Theta\left({k\log k}\right)}$, for both randomized protocols with constant
error probability as well as deterministic protocols (and thus also randomized
protocols with $1/\textrm{poly}(k)$ error probability). Moreover, for
randomized protocols with $1/\textrm{poly}(k)$ error probability, Viola’s
$\Omega(k\log k)$ lower bound holds even for a product distribution on the
inputs (where if $\sum_{i}x_{i}\mod p\notin\\{0,1\\}$ the output can be
arbitrary). We observe that under any partition of the inputs into $2$-players
Alice and Bob, the problem can be solved with ${{O}\left({\log k}\right)}$
bits with probability $1-1/\textrm{poly}(k)$ just by running an equality test
on the sum modulo $p$ of Alice and the negated sum modulo $p$ of Bob. Thus,
this illustrates that the factor $O(k)$ gap for protocols for product input
distributions with $1/\textrm{poly}(k)$ error probability is optimal.

On the other hand, for constant error protocols and a product input
distribution, there is a $2$-player ${{O}\left({1}\right)}$ bit upper bound in
the public coin model which comes from running an equality test with constant
error probability (since we measure error with respect to an input
distribution, equality has an $O(1)$ upper bound with constant error). We note
that the $k$-player protocol has communication ${\Omega\left({k\log
k}\right)}$ for constant error protocols, which gives the ${\Omega\left({k\log
k}\right)}$ factor gap we claimed. The only downside is that the
${\Omega\left({k\log k}\right)}$ lower bound holds for an input distribution
which is product on $k-1$ out of $k$ players, rather than all $k$ players. We
leave it as an open question to give an optimal separation for product input
distributions for constant error probability.

Given the importance of Viola’s problem in showing separations, we next show a
direct sum theorem for his problem, showing its communication complexity
increases to ${\Omega\left({kr\log k}\right)}$ for solving a constant fraction
of $r$ independent copies. To show the direct sum theorem for Viola’s problem,
one issue is that, unlike for two players where the technique of information
complexity often provides direct sum theorems, for $k$-players the analogues
are much weaker. A natural route would be to take Viola’s corruption bound,
argue it implies a high information bound, and then apply standard direct sum
theorems for information. This approach does not give an information cost
lower bound on private coin protocols, though one can fix it for two players
using [5], which improves upon a bound in [6]. However, for $k$ players
similarly strong bounds are unknown. Another natural approach is to use the
fact that if a problem has a corruption bound, then one immediately has a
direct sum for it [4]. Again though, this is only for two players or the
_number on forehead_ model, and not for our setting.

Instead, our proof is inspired by Viola’s rectangle argument for a single copy
of the Sum-Equal problem, where each rectangle, restricted to the first $k-1$
players, is a product distribution on which the protocol generates a message
to the $k$-th player. We use a rectangle argument on multiple copies where the
output is now a binary vector instead of a single bit. The main obstacle is
that we must consider the Hamming distance between the protocol output and the
correct answer in a vector space, which is much more involved than studying
the error probability for a single instance. The intuition of our proof is
that for every large rectangle, there must be linearly many copies that appear
(almost) uniformly random in the last player’s view. The above argument is
fairly intricate, and involves several levels of conversion: i) a large
rectangle implies large conditional entropy in many players’ inputs; ii) the
large entropy of all copies implies we have min-entropy at least $1$ on many
copies; iii) a random variable of min-entropy at least $1$ can always be
decomposed into a convex combination of uniform distributions over two
elements; iv) the summation of sufficiently many independent random variables
that are each drawn from a uniform-over-two-element distribution turns out to
be nearly uniform, and hence many Sum-Equal copies look uniform to the last
player.

Thus, the last player can hardly outperform a random guess. Note that it is
insufficient to prove uniformity for many copies individually (which is not
too hard using the same idea as in Viola’s proof), since such a situation
could be simulated with a much smaller rectangle with very small error. We
instead perform our rectangle argument inductively to show most copies appear
almost uniform, even if conditioned on previous copies.

This direct sum technique has further applications. One application is to
proving a lower bound for approximating the Hamming norm in a strict turnstile
stream. Using a result of [2], to show lower bounds for streaming algorithms
in the strict turnstile model, it suffices to show lower bounds in the
simultaneous communication model, where each player simultaneously sends a
message to a referee who outputs the answer. While our direct sum theorem
holds in this more restrictive model, we also need to consider a composition
of the gap-Hamming problem on top of the Sum-Equal instances as well as an
augmented index version of the composed problem. In the augmented problem we
additionally give a referee an index $i$ and the answers to all copies $j$,
with $j>i$. Similar augmentation has been studied for $L_{p}$-norms [12]. This
allows us to reduce our communication problem to Hamming norm approximation,
and ultimately prove our data stream lower bound.

##  2 Preliminaries

A function $f:\Sigma^{k}\to\Gamma$ is called a _$k$ -party symmetric function_
if for every $(x_{1},x_{2},\dots,x_{k})\in\Sigma^{k}$ and for every
permutation $\sigma$ over ${\left\\{{1,2,\dots,k}\right\\}}$, there is
$f(x_{1},\dots,x_{k})=f\left(x_{\sigma(1)},\dots,x_{\sigma(k)}\right).$ A
$k$-dimensional vector space $S$ is called a _product space_ if it can be
represented as $S=S_{1}\times S_{2}\times\dots\times S_{k}$. A distribution
$\mu$ is called a _product distribution_ if it is obtained by taking the
product of $k$ independent distributions, i.e.,
$\mu=\mu_{1}\times\mu_{2}\times\dots\times\mu_{k}$.

In the $t$-player communication complexity model, there are $t$
computationally unbounded players, e.g., $P_{1},\dots,P_{t}$, required to
compute a function $f:X_{1}\times\dots\times X_{t}\to Y$, where $f$ is usually
a $t$-party symmetric function. Each player $P_{i}$ is given a private input
$x_{i}\in X_{i}$ and follows a fixed protocol to exchange messages. For every
input $(x_{1},\dots,x_{t})$, the message transcript is denoted by
$\Pi_{t}(x_{1},\dots,x_{t})$ when all players follow the protocol $\Pi_{t}$
(when $\Pi_{t}$ is randomized, $\Pi_{t}(x_{1},\dots,x_{t})$ is a random
variable taking probabilities over players’ random coins). A deterministic
protocol $\Pi_{t}$ computes $f$ if there is a function $\Pi_{out}$ such that
$\Pi_{out}\left(\Pi_{t}^{(t)}(x_{1},\dots,x_{t}),x_{t}\right)\equiv f$, where
$\Pi_{t}^{(t)}(x_{1},\dots,x_{t})$ denotes $P_{t}$’s view under the execution
of $\Pi_{t}$ on input $(x_{1},\dots,x_{t})$ and for simplicity we let
$\Pi_{out}\left(x_{1},\dots,x_{t}\right):=\Pi_{out}\left(\Pi_{t}^{(t)}(x_{1},\dots,x_{t}),x_{t}\right)$.
A $\delta$-error randomized protocol $\Pi_{t}$ for $f$ requires the existence
of $\Pi_{out}$ such that for all inputs $(x_{1},\dots,x_{t})$,
$\Pr\left[\Pi_{out}\left(x_{1},\dots,x_{t}\right)=f(x_{1},\dots,x_{t})\right]\geq
1-\delta$. The _communication cost_ of $\Pi_{t}$ is the maximum size of
$\Pi_{t}(x_{1},\dots,x_{t})$ over all $x_{1},\dots,x_{t}$ and all random
coins. The _$t$ -player deterministic communication complexity_ (resp. _$t$
-player $\delta$-error randomized communication complexity_), denoted by
$\mathbf{DCC}_{t}(f)$ (resp. $\mathbf{RCC}_{t,\delta}(f)$), is the cost of the
best $t$-player deterministic (resp. $\delta$-error randomized) protocol
$\Pi_{t}$ for $f$.

Given a $k$-party function $f:X_{1}\times\dots\times X_{k}\to Y$ and $t<k$, we
define $\mathbf{DCC}_{t}(f)$ and $\mathbf{RCC}_{t,\delta}(f)$ under a _worst-
case partition_ of inputs. That is, let
$f_{t}(z_{1},\dots,z_{t})=f(x_{1},\dots,x_{k})$ be defined for every partition
$i_{0}=0\leq i_{1}\leq\dots\leq i_{t}=k$ and
$z_{j}:=(x_{i_{j-1}+1},\dots,x_{i_{j}})$, and the $t$-player communication
complexity of $f$ is defined with respect to the worst choice of $f_{t}$,
i.e., $\mathbf{DCC}_{t}(f):=\max_{f_{t}}\mathbf{DCC}_{t}(f_{t})$ and
$\mathbf{RCC}_{t,\delta}(f):=\max_{f_{t}}\mathbf{RCC}_{t,\delta}(f_{t})$.

Given a $t$-party function $f$ and its input distribution $\mu$, we let
$\mathbf{DCC}^{\mu}_{t,\delta}(f)$ denote the communication cost of the best
$t$-player deterministic protocol $\Pi_{t}$ computing $f$ such that
$\Pr_{x\sim\mu}\left[\Pi_{out}(x)\neq f(x)\right]\leq\delta$. Similarly we
define $\mathbf{RCC}^{\mu}_{t,\delta}(f)$ for randomized protocols.

In the restricted _one-way communication model_ [18, 1, 14], the $i$-th player
sends exactly one message to the $(i+1)$-st player for $i\in[t-1]$ following
$\Pi_{t}$, and then $P_{t}$ announces the output of $\Pi_{t}$ as specified by
$\Pi_{out}$. Note that in this setting there are only $k-1$ messages sent by
$P_{1},\dots,P_{k-1}$, and we do not count the final output announced by
$P_{t}$ in the communication in order to best correspond to streaming
algorithms. This is also known as a _sententious_ protocol in previous work,
e.g., [19]. We denote the _$t$ -player one-way communication complexities of
$f$_ by $\overrightarrow{\mathbf{DCC}}_{t}(f)$ and
$\overrightarrow{\mathbf{RCC}}_{t,\delta}(f)$, respectively.

In the _common reference string model_ (aka _CRS model_), there is a sequence
of public random coins, which is by default a uniformly random binary string,
accessible to all players. The obvious advantage of communication in the CRS
model is that players have access to the same random string and thus save the
cost of synchronizing their private coins.

A streaming algorithm is an algorithm that scans the input
$(x_{1},\dots,x_{m})\in\Sigma^{m}$ as $m$ stream input items in sequence,
updates its internal memory of size $s={o\left({m\log|\Sigma|}\right)}$ (i.e.,
a streaming automaton with $2^{s}$ states, where the space cost of updating
the internal memory is not accounted for), and finally outputs a function
$f(x_{1},\dots,x_{m})$ evaluated on all input items. If the best deterministic
(resp. $\delta$-error randomized) streaming algorithm computes $f$ with $s$
bits of memory and $t$ passes over the data stream, then we say the
_deterministic_ (resp. _$\delta$ -error_) _streaming complexity_ of $f$ is
$st$, denoted by $\mathbf{DSC}(f)=st$ (resp. $\mathbf{RSC}_{\delta}(f)=st$).
In a popular and standard setting, a streaming algorithm scans the input
stream in a _single pass_ and only processes every input item once. The
necessary amount of memory required by such single-pass algorithms is called
the _single-pass deterministic/ $\delta$-error streaming complexity_ and
denoted by $\overrightarrow{\mathbf{DSC}}(f)$ and
$\overrightarrow{\mathbf{RSC}}_{\delta}(f)$ respectively.

Note that every streaming algorithm can be naturally interpreted as a
communication protocol where each party holds some (possibly an empty set of)
input items on the stream and the messages capture the memory updates. The
connection between streaming complexity and communication complexity trivially
follows in the following lemma.

######  Lemma 2.1.

For every function $f$ and error tolerance $\delta$, for every
$k\in\mathbb{N}$, it holds that:

$\mathbf{DSC}(f)\geq\frac{1}{k}\cdot\mathbf{DCC}_{k}(f),\;\;\mathbf{RSC}_{\delta}(f)\geq\frac{1}{k}\cdot\mathbf{RCC}_{k,\delta}(f)$

Furthermore, similar relations hold for single-pass streaming complexities
versus $k$-player one-way communication complexities:

$\overrightarrow{\mathbf{DSC}}(f)\geq\frac{1}{k-1}\cdot\overrightarrow{\mathbf{DCC}}_{k}(f),\;\;\overrightarrow{\mathbf{RSC}}_{\delta}(f)\geq\frac{1}{k-1}\cdot\overrightarrow{\mathbf{RCC}}_{k,\delta}(f)$

##  3 Communication Complexity for Functions on Non-Product Spaces

######  Theorem 3.1.

For every $t\geq 2$, there is a $t$-party symmetric function $f:D\to\\{0,1\\}$
defined on $D\subseteq\\{0,1\\}^{n}=\left(\\{0,1\\}^{n/t}\right)^{t}$ such
that for every error tolerance $\delta<1/4$,
$\overrightarrow{\mathbf{DCC}}_{t-1}(f)\leq t-1$ but
$\mathbf{RCC}_{t,\delta}(f)={\Omega\left({n/t}\right)}$. In particular, as
long as $t={{O}\left({1}\right)}$ is a constant, we have
$\overrightarrow{\mathbf{DCC}}_{t-1}(f)={{O}\left({1}\right)}$ and
$\mathbf{RSC}_{\delta}(f)\geq{\frac{1}{t}\cdot\mathbf{RCC}_{t,\delta}(f)}={\Omega\left({n}\right)}$.

######  Proof 3.2.

Consider the $t$-party set disjointness problem $\textsc{Disj}_{n/t,t}$
defined as follows: there are $t$ players $P_{1},\dots,P_{t}$ such that every
player $P_{i}$ holds a private indicator vector
$\mathbf{x}_{i}\in\\{0,1\\}^{n/t}$ which represents a subset of $[n/t]$, i.e.,
$\textsc{Disj}_{n/t,t}(\mathbf{x}_{1},\dots,\mathbf{x}_{t})=\vee_{j=1}^{n/t}\left(\wedge_{i=1}^{t}x_{i,j}\right)$,
where $x_{i,j}$ denotes the $j$-th coordinate of $\mathbf{x}_{i}$. We consider
the domain $D$ such that the vectors
$\mathbf{x}_{1},\dots,\mathbf{x}_{t}\in\\{0,1\\}^{n/t}$ are either (1)
pairwise disjoint, or (2) sharing a unique element $j\in[n/t]$. Let $f$ be the
function that computes $\textsc{Disj}_{n/t,t}$ on domain $D$.

On the one hand, it is easy to verify that
$\overrightarrow{\mathbf{DCC}}_{t-1}(f)\leq t-1$. Indeed, at least one of the
$t-1$ players obtains two distinct indicator vectors and hence can itself
decide the output of $f$. The communication is $1$ bit per player to pass the
result, and hence the total communication is bounded by $t-1$ since there are
$t-1$ players.

On the other hand, the $\Omega(n/t)$ lower bound for
$\mathbf{RCC}_{t,\delta}(f)$ follows from the known lower bound for multi-
player set disjointness (see [3], which was improved to optimal in [8, 10]).
The lower bound for $\mathbf{RSC}_{\delta}(f)$ immediately follows by Lemma
2.1.

##  4 Deterministic Communication and Streaming Complexity

We first show that 2-player one-way communication complexity is equivalent to
the streaming complexity of single-pass streaming algorithms in the
deterministic setting.

######  Theorem 4.1.

For every symmetric function $f:\Sigma^{m}\to\Gamma$,
$\overrightarrow{\mathbf{DCC}}_{2}(f)\leq\overrightarrow{\mathbf{DSC}}(f)\leq\overrightarrow{\mathbf{DCC}}_{2}(f)+\log
m$.

######  Proof 4.2.

Obviously,
$\overrightarrow{\mathbf{DSC}}(f)\geq\overrightarrow{\mathbf{DCC}}_{2}(f)$
since a 2-player communication protocol simulates a streaming algorithm. It
remains to prove
$\overrightarrow{\mathbf{DSC}}(f)\leq\overrightarrow{\mathbf{DCC}}_{2}(f)+\log
m$.

Suppose the input stream is $(x_{1},\dots,x_{m})\in\Sigma^{m}$, and for every
partition into $(x_{1},\dots,x_{i})$ and $(x_{i+1},\dots,x_{k})$ there is a
deterministic 2-player one-way protocol $\Pi_{2}^{i}$ computing $f$. We design
the deterministic single-pass streaming algorithm $A$ for $f$ by simulating
$2$-player one-way communication protocols under different partitions. The
memory usage of $A$ is therefore bounded by the maximum communication cost of
the simulated $2$-player protocols plus an index in $[m]$ recording the number
of processed items.

Notice that when processing the item $x_{i+1}$, $A$ has already processed
$x_{1},\dots,x_{i}$ and has $(m_{i},i)$ in memory. $A$ can thus reconstruct a
compatible guess of $x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i}$ that
would induce exactly the message $m_{i}$ as in $\Pi_{2}^{i}$, and then sets
the memory to be $(m_{i+1},i+1)$ where $m_{i+1}$ is the message sent in
$\Pi_{2}^{i+1}$ when $P_{1}$ has
$(x^{\prime\prime}_{1},\dots,x^{\prime\prime}_{i},x_{i+1})$ and $P_{2}$ has
$(x_{i+2},\dots,x_{m})$. $A$ repeats this process for every $i=1,\dots,m-1$
and at the end it outputs $f(x_{1},\dots,x_{m})$.

Therefore, we complete the proof with
$\overrightarrow{\mathbf{DCC}}_{2}(f)\leq\overrightarrow{\mathbf{DSC}}(f)\leq\overrightarrow{\mathbf{DCC}}_{2}(f)+\log
m$.

Note that the additional index $i$ in the above simulation, which results in
the additive $\log m$ term in the upper bound, indicates which $2$-player
protocol should be simulated in the reconstruction, and it is implicitly
shared in the $2$-player communication case when $m$ is a common knowledge.
For functions that are well-defined for an arbitrary number of input items,
e.g. the parity function, this index can be saved, and hence
$\overrightarrow{\mathbf{DSC}}(f)=\overrightarrow{\mathbf{DCC}}_{2}(f)$.

For communication complexity among more players, we establish the following
corollary.

######  Corollary 4.3.

For every $k$-party symmetric function $f$,

$(k-1)\cdot\overrightarrow{\mathbf{DCC}}_{2}(f)\leq\overrightarrow{\mathbf{DCC}}_{k}(f)\leq(k-1)\cdot\left(\overrightarrow{\mathbf{DCC}}_{2}(f)+\log
k\right)$

######  Proof 4.4.

Combining Lemmas 2.1 and 4.1, it follows that

$\overrightarrow{\mathbf{DCC}}_{k}(f)\leq(k-1)\cdot\overrightarrow{\mathbf{DSC}}(f)\leq(k-1)\cdot\left(\overrightarrow{\mathbf{DCC}}_{2}(f)+\log
k\right)$

The other direction
$\overrightarrow{\mathbf{DCC}}_{k}(f)\geq(k-1)\cdot\overrightarrow{\mathbf{DCC}}_{2}(f)$
holds by giving $z_{j}=\emptyset$ to every player
$j\in{\left\\{{2,\dots,k-1}\right\\}}$ in the $k$-player case, when the
problem degenerates to $2$-player communication but the same message has to be
passed $k-1$ times.

Such a linear separation naturally extends to the communication complexity of
$t$-player versus $k$-player protocols, as long as $2\leq t<k$. Thus, the
deterministic communication complexity grows _linearly_ in the number of
parties.

We remark that if every player must get a non-trivial input, i.e., at least
one input element to the function, the linear growth remains for some but not
all problems. For example, the communication complexity of the parity of $k$
bits is linear in the number of players. However, to decide whether $k$
elements in $[k]$ are distinct, the $2$-player protocol requires communication
$\log\binom{k}{k/2}\approx k-\log\sqrt{k}$, whereas the $k$-player worst-case
communication grows sublinearly, i.e. for $k$ players the communication is no
more than $\sum_{i=1}^{k-1}\log\binom{k}{i}\ll(k-1)\cdot\log\binom{k}{k/2}$.

##  5 Communication Complexity for Functions on a Product Space

###  5.1 Separations for Randomized Communication Complexity

In this section, we consider the communication cost of randomized multi-player
protocols defined on product input distributions and present a $k\log k$
versus $t\log t$ separation between $k$-player and $t$-player communication
complexity.

First we introduce the Sum-Equal problem (as used in Viola’s work [19]).

######  Definition 5.1.

The _$k$ -player Sum-Equal over integers_, denoted by $\textsc{Sum-
Equal}_{k}$, requires deciding whether $\sum_{i=1}^{k}x_{i}=0$, where each
player $P_{i}$ is given an integer $x_{i}$ as his private input together with
the integer $k$ as public input shared by all players. In the CRS model, an
additional public random string is also known to all players. The _$k$ -player
Sum-Equal over $\mathbb{Z}_{m}$_, denoted by $\textsc{Sum-Equal}_{k,m}$, is
defined similarly as $\textsc{Sum-Equal}_{k}$, except that the input items are
drawn from $\mathbb{Z}_{m}$ and the summation is over $\mathbb{Z}_{m}$, for a
publicly known $m$.

######  Lemma 5.2 ([19], Theorem 15 and Theorem 29).

For every $k\in\mathbb{N}$, $0\leq\delta\leq 1/3$, and in the CRS model, the
$k$-player $\delta$-error communication complexity of Sum-Equal satisfies:

For every $m\in\mathbb{N}$,
$\overrightarrow{\mathbf{RCC}}_{k,\delta}(\textsc{Sum-
Equal}_{k,m})={{O}\left({k\log(k/\delta)}\right)}$.

For every prime $p\in(k^{1/4},2k^{1/4})$,
$\mathbf{RCC}_{k,\delta}(\textsc{Sum-Equal}_{k,p})={\Omega\left({k\log
k}\right)}$.111Viola’s states the lower bound for constant $\delta$, but it
naturally holds for smaller $\delta$ (sometimes not tight).

In particular, $\mathbf{RCC}_{k,\delta}(\textsc{Sum-
Equal}_{k,p})={\Theta\left({k\log k}\right)}$ in the CRS model if
$\delta={\Omega\left({1/\mathsf{poly}(k)}\right)}$.

We remark that Viola’s lower bound for $\textsc{Sum-Equal}_{k,p}$ is proved
for a non-product distribution $\mu_{H}$ whose support covers exactly a $2/p$
fraction of the whole (product) input space. Thus if a $k$-player protocol
solves $\textsc{Sum-Equal}_{k,p}$ with error $\delta\leq 1/k$ on a uniform
distribution $\mu$ over the whole input space, then its error with respect to
$\mu_{H}$ is bounded by $\frac{1/k}{2/p}<k^{-3/4}$. Notice that the two player
version of $\textsc{Sum-Equal}_{k,p}$ degenerates to testing equality over
$\mathbb{Z}_{p}$ whose upper bound is ${{O}\left({\log(1/\delta)+\log\log
k}\right)}$, see more details in Appendix A. By Lemma 5.2, the
${\Omega\left({k}\right)}$ separation in Corollary 5.3 naturally follows.

######  Corollary 5.3.

For every prime $p\in(k^{1/4},2k^{1/4})$ and $\delta\leq 1/\mathsf{poly}(k)$,
there is a product distribution $\mu$ such that
$\mathbf{RCC}_{k,\delta}^{\mu}(\textsc{Sum-Equal}_{k,p})={\Omega\left({k\log
k}\right)}$, $\overrightarrow{\mathbf{RCC}}_{2,\delta}(\textsc{Sum-
Equal}_{k,p})={{O}\left({\log k}\right)}$.

For a larger error tolerance, say $\delta$ is a constant, we have a stronger
separation between $k$-party communication and $t$-party communication.
However, the hard distribution is slightly non-product, that is, it is a
product distribution on any $k-1$ out of the $k$ players.

######  Corollary 5.4.

For every $k\in\mathbb{N}$, there is a $k$-party symmetric function $f$ such
that

For any product distribution $\mu$, for every $2\leq t\leq k$ and
$0\leq\delta\leq 1/3$,
$\overrightarrow{\mathbf{RCC}}_{t,\delta}^{\mu}(f)={{O}\left({t\log(t/\delta)}\right)}$.
In particular,
$\overrightarrow{\mathbf{RCC}}_{2,\delta}^{\mu}(f)={{O}\left({\log(1/\delta)}\right)}$.

There exists a distribution $\mu_{H}$, which is product on any $k-1$ out of
$k$ players, for which $\mathbf{RCC}_{k,\delta}^{\mu}(f)={\Omega\left({k\log
k}\right)}$ as long as $\delta\leq 1/3$.

For $\delta\geq 1/\mathsf{poly}(t)$, the gap between
$\mathbf{RCC}_{k,\delta}^{\mu}(f)$ and
$\overrightarrow{\mathbf{RCC}}_{t,\delta}^{\mu}(f)$ is bounded as below:

$\mathbf{RCC}_{k,\delta}^{\mu}(f)\;\big{/}\;\overrightarrow{\mathbf{RCC}}_{t,\delta}^{\mu}(f)={\Omega\left({\frac{k\log
k}{t\log t}}\right)}$

The outline of the proof of Corollary 5.4 was given in Section 1. That is, the
upper bound in part (a) follows from applying $k=t$ in the first part of Lemma
5.2, while the lower bound in part (b) follows from the second part of Lemma
5.2.

###  5.2 Tightness of the Communication Complexity Separation

The following theorem and corollary show tightness of our separations.

######  Theorem 5.5.

For every $k$-party function $f:\Sigma^{k}\to\Gamma$, product distribution
$\mu$ over $\Sigma^{k}$, and error tolerance $\delta<1/3$, if the optimal
$\delta$-error $2$-player one-way protcol for $f$ does not degenerate to the
deterministic case, then the following holds:

$\displaystyle{\overrightarrow{\mathbf{RCC}}_{k,\delta}^{\mu}(f)}\;\big{/}\;{\overrightarrow{\mathbf{RCC}}_{2,\delta}(f)}\leq$
$\displaystyle{{O}\left({k\cdot\left(1+\frac{\log
k}{\log(1/\delta)}\right)}\right)}=\begin{cases}{{O}\left({k\log
k}\right)}&\mbox{if $\delta={{\Omega\left({1}\right)}}$}\\\
{{O}\left({k}\right)}&\mbox{if
$\delta=1/k^{{\Omega\left({1}\right)}}$}\end{cases}$

In particular,

$\displaystyle\overrightarrow{\mathbf{RCC}}_{k,\delta}^{\mu}(f)=$
$\displaystyle\begin{cases}{{O}\left({k\log
k}\right)}\cdot\overrightarrow{\mathbf{RCC}}_{2,\delta}(f)&\mbox{if
$\delta={{\Omega\left({1}\right)}}$}\\\
{{O}\left({k}\right)}\cdot\overrightarrow{\mathbf{RCC}}_{2,\delta}(f)+{{O}\left({k\log
k}\right)}&\mbox{if $\delta\leq 1/k^{{\Omega\left({1}\right)}}$}\end{cases}$

######  Proof 5.6.

First we let $\Pi_{0}$ be the optimal $\delta$-error $2$-player one-way
protocol $\Pi_{0}$ that computes $f$ with communication
$C=\overrightarrow{\mathbf{RCC}}_{2,\delta}(f)$, and construct a new protocol
$\Pi_{2}$ by taking the majority of $M$ independent parallel copies of
$\Pi_{0}$ such that $\Pi_{2}$ has error $\varepsilon=\delta^{2}/(16k^{2})$ and
communication ${CM}$. Recall that $\Pi_{0}$ has $\delta<1/3$, it suffices to
let $t$ and $M$ in Lemma 5.7 be as follows:

$\displaystyle t$
$\displaystyle={\left\lceil{\log\left(\delta/(16k^{2})\right)/\log\left(4\delta(1-\delta)\right)}\right\rceil}$
(1) $\displaystyle M$
$\displaystyle=1+2t=1+2{\left\lceil{\frac{\log(1/\delta)+2\log
k+4}{\log(1/\delta)+\log(1/(1-\delta))-2}}\right\rceil}={\Theta\left({1+\frac{\log
k}{\log(1/\delta)}}\right)}$ (2)

######  Lemma 5.7.

Let $t\in\mathbb{N}$ and $X_{1},X_{2},\dots,X_{2t+1}$ be i.i.d. binary random
variable such that $\Pr[X_{i}=1]=\delta<1/2$ for every $i\in[t]$, and let
$Y=\mathbf{Majority}{\left\\{{X_{1},\dots,X_{2t+1}}\right\\}}$ be the majority
of all $X_{i}$’s. Then $\Pr[Y=1]\leq\varepsilon$ as long as
$t\geq\log(\varepsilon/\delta)/\log(4\delta(1-\delta))$.

######  Proof 5.8.

For $0<\delta<1/2$ and
$t\geq\log(\varepsilon/\delta)/\log(4\delta(1-\delta))$, we have

$\displaystyle\Pr\left[Y=1\right]$
$\displaystyle=\Pr\left[|{\left\\{{i\;|\;X_{i}=1}\right\\}}|\geq t+1\right]$
$\displaystyle=\sum_{j=t+1}^{2t+1}\binom{2t+1}{j}\delta^{j}(1-\delta)^{2t+1-j}$
$\displaystyle\leq\sum_{j=t+1}^{2t+1}\binom{2t+1}{j}\delta^{t+1}(1-\delta)^{t}$
$\displaystyle=\frac{2^{2t+1}}{2}\cdot\delta^{t+1}(1-\delta)^{t}=\left(4\delta(1-\delta)\right)^{t}\cdot\delta$
$\displaystyle\leq\frac{\varepsilon}{\delta}\cdot\delta=\varepsilon$

The first inequality holds because $\delta<1/2$ and hence
$\delta^{j}(1-\delta)^{2t+1-j}\leq\delta^{t+1}(1-\delta)^{t}$ for $j\geq t+1$.
The second inequality holds because $4\delta(1-\delta)<1$ for $\delta<1/2$,
and
$\left(4\delta(1-\delta)\right)^{t}\leq\left(4\delta(1-\delta)\right)^{\log(\varepsilon/\delta)/\log(4\delta(1-\delta))}=\varepsilon/\delta$.
Thus, we have proved that $\Pr[Y=1]\leq\varepsilon$ for
$t\geq{\log(\varepsilon/\delta)/\log(4\delta(1-\delta))}$.

Note that $\Pi_{2}$ is still a $2$-player one-way protocol but has
communication ${CM}$. Furthermore, we remark that $CM={\Omega\left({\log
k}\right)}$ for $\delta>0$, since the error probability must be $\delta\geq
1/2^{C}$ if it is not zero, and hence $M={\Theta\left({1+\frac{\log
k}{\log(1/\delta)}}\right)}={\Omega\left({1+\frac{\log k}{C}}\right)}$.

Second we prove that for every product input distribution $\mu$ over
$\Sigma^{k}$, the $k$-party function $f$ can be evaluated by a randomized
$k$-player one-way protocol $\Pi_{k}$ with communication
${{O}\left({k\cdot(CM+\log k)}\right)}$ and error $\delta/2$ with respect to
$\mu$. The idea is that given the product input distribution $\mu$, each
player $P_{i}$ acts as follows:

  1. 1.

$P_{i}$ first assumes that the received message $m_{i-1}$ from $P_{i-1}$ will
lead to a correct answer with probability $\geq 1-\frac{\delta}{4k}$ with
respect to $\mu$.

  2. 2.

$P_{i}$ samples a possible input $x^{\prime}_{1},\dots,x^{\prime}_{i-1}$ of
previous players $P_{1},\dots,P_{i-1}$, such that if Alice gets input
$(x^{\prime}_{1}\dots,x^{\prime}_{i-1})$ and sends $m_{i-1}$, then with
probability $\geq 1-\frac{\delta}{4k}$ the protocol $\Pi_{2}$ leads the
correct answer. The probability is taken over internal randomness and Bob’s
input following the marginal distribution of $\mu$ on the remaining players
(here we use the condition that $\mu$ is a product distribution).

  3. 3.

Finally, $P_{i}$ sends a message $(m_{i},i)$ of length $CM+\log
k={{O}\left({CM}\right)}$, where $m_{i}$ is the message that Alice would send
in $\Pi_{2}$ when her input is
$(x^{\prime}_{1},\dots,x^{\prime}_{i-1},x_{i})$.

By a union bound the error probability of $\Pi_{k}$ is bounded by
$k\cdot(\frac{\delta}{4k}+\frac{\delta}{4k})<\delta/2$ with respect to $\mu$.
The fact that $\mu$ is a product distribution is used in the second step where
the sampling process relies on that previous players’ inputs are independently
distributed from that of future players.

Thus we finish the proof and conclude that
$\overrightarrow{\mathbf{RCC}}_{k,\delta}^{\mu}(f)\leq{{O}\left({kCM}\right)}$.

Notice that in the proof of Theorem 5.5, every message in $\Pi_{k}$ has the
length bounded by ${{O}\left({CM}\right)}$, which gives an upper bound for the
single-pass streaming complexity.

######  Corollary 5.9.

For every $k$-party function $f$ and product input distribution $\mu$, and for
every $\delta<1/3$,
$\mathbf{RSC}_{\delta}^{\mu}(f)\leq\overrightarrow{\mathbf{RSC}}_{\delta}^{\mu}(f)\leq{{O}\left({1+\frac{\log
k}{\log(1/\delta)}}\right)}\cdot\overrightarrow{\mathbf{RCC}}_{2,\delta}(f).$

##  6 A Direct Sum for Viola’s Problem

We next turn to our direct sum theorem for Viola’s problem, which is a crucial
building block for our streaming application. Note that the theorem is proved
for $\delta<1/9$, but lower bounds for large error tolerance such as
$\delta=1/3$ can be obtained using a standard error amplification argument.

######  Theorem 6.1.

Let $F:\left(\mathbb{Z}_{p}^{m}\right)^{k}\to\\{0,1\\}^{m}$ be the $k$-party
function computing $m$ independent copies of $\textsc{Sum-Equal}_{k,p}$, where
$p$ is a prime between $k^{1/4}$ and $2k^{1/4}$. For every error tolerance
$\delta\in(0,1/9)$, we say a protocol $\Pi$ is _correct with probability
$1-\delta$_ if there is a reconstruction function $G$ such that for every
fixed $i\in[m]$ and input $x\in\left(\mathbb{Z}_{p}^{m}\right)^{k}$,
$G\big{(}i,\Pi_{out}(x)\big{)}$ equals the output of the $i$-th instance of
$\textsc{Sum-Equal}_{k,p}$ with probability at least $1-\delta$, over the
internal randomness of $\Pi$. Then the communication cost of any $\Pi$ which
is correct with probability $1-\delta$, is ${\Omega\left({mk\log k}\right)}$.

######  Proof 6.2.

For simplicity of notation in the proof, we flip the output of $F$, so that it
outputs $0$ if the input to the corresponding $\textsc{Sum-Equal}_{k,p}$
instance sums to $0$ in $\mathbb{Z}_{p}$ and that instance outputs $1$, and
$F$ outputs $1$ on instances with summation other than $0$.

Let $\Pi$ be an $\delta$-error randomized protocol for $F$, and let
$\Pi_{out}\left(x\right)$ denote the output of $\Pi$ on input $x$. Here by
“the $\delta$-error protocol” we mean that the expected error rate of $\Pi$ is
bounded by $\delta$, since both $\Pi_{out}(x)$ and $F(x)$ are binary vectors
in $\\{0,1\\}^{m}$. Therefore,

$\displaystyle\Pr_{i\in_{R}[m]}\left[\Pi_{out}\left(x\right)_{i}\neq
F_{i}(x)\right]\leq\delta$

where the input to $F$ is partitioned as
$x=\left(x^{(1)},x^{(2)},\dots,x^{(m)}\right)\in\mathbb{Z}_{p}^{m\times k}$
such that $F_{i}(x):=\overline{\textsc{Sum-Equal}_{k,p}}(x^{(i)})$ computes
the $i$-th instance of $\textsc{Sum-Equal}_{k,p}$ for each $i\in[m]$.

We abuse notation a little in this proof and let $|\cdot|$ denote the _Hamming
weight_ of a not necessarily binary vector, which measures the number of non-
zero coordinates of the vector. Then,

$\displaystyle\mathbf{E}\left[\left|\Pi_{out}\left(x\right)-F(x)\right|\right]\leq\delta
m$

To prove that
$\mathbf{RCC}_{k,\delta}(F)=\max_{x}|\Pi(x)|={\Omega\left({mk\log k}\right)}$
for the optimal $\delta$-error protocol $\Pi$, we will deduce a contradiction
if $\Pi$ uses $c<\gamma mk\log k$ bits of communication, for a constant
$\gamma=(1-9\delta)/135>0$ and sufficiently large $k$. Thus, we can conclude a
communication lower bound of $c\geq\gamma mk\log k={\Omega\left({mk\log
k}\right)}$.

For the contradiction, we first convert the randomized protocol $\Pi$ into a
deterministic protocol $\Pi^{\prime}$ that has small error with respect to a
specific distribution $\mathcal{H}$. The deterministic protocol $\Pi^{\prime}$
is obtained by fixing all internal random coins of $\Pi$ so that
$\Pi^{\prime}$ has error rate at most $\delta$ for inputs drawn from
$\mathcal{H}$.

$\displaystyle\mathbf{E}_{X\sim\mathcal{H}}\left[\left|\Pi^{\prime}_{out}(X)-F(X)\right|\right]\leq\delta
m$

Since $\Pi^{\prime}$ can never generate a transcript larger than the
communication that $\Pi$ uses in the worst case, i.e.,
$|\Pi^{\prime}(X)|\leq\max_{x}|\Pi(x)|=c$, it suffices to prove the
communication lower bound for $\Pi^{\prime}$.

By Markov’s inequality, we have that for every positive constant
$\varepsilon>0$,

$\displaystyle\Pr_{X\sim\mathcal{H}}\left[\left|\Pi^{\prime}_{out}(X)-F(X)\right|>\varepsilon
m\right]\leq\frac{\mathbf{E}_{X\sim\mathcal{H}}\left[\left|\Pi^{\prime}_{out}(X)-F(X)\right|\right]}{\varepsilon
m}\leq\frac{\delta}{\varepsilon}$ (3)

Now we specify the distribution $\mathcal{H}$. Let $G$, $B$ be defined as

$\left\\{\begin{array}[]{c c
r}G:=&\big{(}G_{1},\dots,G_{k-1},&-\sum_{j=1}^{k-1}G_{j}\big{)}\\\
B:=&\big{(}B_{1},\dots,G_{k-1},&1-\sum_{j=1}^{k-1}B_{j}\big{)}\end{array}\right.$

for uniform and independent $G_{i},B_{i}\in\mathbb{Z}_{p}$ for every
$j\in[k-1]$. Note that: a) $\textsc{Sum-Equal}_{k,p}(G)=1$, $\textsc{Sum-
Equal}_{k,p}(B)=0$ and hence $F_{i}(G)=0,F_{i}(B)=1$; b) the first $k-1$
elements of $G$ and $B$, denoted by $G_{-k}$ and $B_{-k}$, follow the same
distribution, i.e., the uniform distribution over $\mathbb{Z}_{p}^{k-1}$. For
convenience we can write $B=(G_{-k},1+G_{k})$.

Let $H:=G/2+B/2$ be a mixture of $G$ and $B$ and let $\mathcal{H}$ be $m$
independent copies of $H$ as below:

$\mathcal{H}:=H^{m}=\left(G/2+B/2\right)^{m}$

Since $B=(G_{-k},1+G_{k})$ and $H=G/2+B/2$, we note that

$\mathcal{H}=\sum_{v\in\\{0,1\\}^{m}}\frac{1}{2^{m}}(G^{m}_{-k},v+G^{m}_{k})=(G^{m}_{-k},V+G^{m}_{k}),$

where $G^{m}_{-k}$ is uniformly distributed over
$\mathbb{Z}_{p}^{m\times(k-1)}$, $G_{k}^{m}$ is a vector in
$\mathbb{Z}_{p}^{m}$ such that $G_{k}^{m}=-\sum_{j=1}^{k-1}G^{m}_{j}$, and $V$
is a random variable over $\mathbb{Z}_{p}^{m}$ but follows the uniform
distribution over $\\{0,1\\}^{m}$. With the above notation of $\mathcal{H},V$,
we have

$F(\mathcal{H})=F(G^{m}_{-k},V+G^{m}_{k})=V$

To prove the communication lower bound of a deterministic protocol
$\Pi^{\prime}$ that has error probability $\leq\delta$ w.r.t. $\mathcal{H}$,
we recall the following protocol decomposition by monochromatic rectangles,
c.f. Claim 24 in [19] or Lemma 1.16 in [15].

######  Claim 1 ([19], Claim 24).

A $k$-player (number-in-hand) deterministic protocol using communication $\leq
c$ partitions the inputs into $C\leq 2^{c}$ sets of inputs
$R^{1},R^{2},\ldots,R^{C}$ such that

  * •

the protocol outputs the same value on inputs in the same set, and

  * •

the sets are rectangles: each $R^{i}$ can be written as $R^{i}=R_{1}^{i}\times
R_{2}^{t}\times\ldots\times R_{k}^{i}$ where $R_{j}^{i}$ is a subset of the
inputs of Player $j$.

For every $i\in[C]$ and rectangle $R^{i}$, we use the notation
$R^{i}_{-j}:=R^{i}_{1}\times R^{i}_{2}\times\dots\times R^{i}_{j-1}\times
R^{i}_{j+1}\times\dots\times R^{i}_{k}$ to denote the projection of $R^{i}$ on
to the $k-1$ coordinates except the $j$-th one, for every $j\in[k]$. In
particular, $R^{i}_{-k}:=R^{i}_{1}\times R^{i}_{2}\times\dots\times
R^{i}_{k-1}$ denotes the first $k-1$ coordinates. Sometimes the index $i$ of
rectangle $R^{i}$ is clear from context, for which we simply write $R$ instead
of $R^{i}$.

In what follows we show a contradiction when $\Pi^{\prime}$ has communication
$c<\gamma mk\log k$ and hence there are $C\leq 2^{c}<k^{\gamma tk}$
rectangles. The argument depends on the following lemma, which essentially
guarantees that for every large rectangle, $\Pi^{\prime}$ is likely to make
mistakes on more than $\varepsilon m$ coordinates.

######  Lemma 6.3.

For every rectangle $R$ satisfying $\Pr[\mathcal{H}_{-k}\in
R_{-k}]\geq\frac{1}{\alpha C}>\frac{1}{\alpha k^{\gamma mk}}$ for which
$\alpha=p^{{{O}\left({1}\right)}}$, there must be a set $L\subseteq[m]$ such
that $|L|=(1-135\gamma)m$ and $G_{k}^{(L)}\;|\;G_{-k}^{m}\in R_{-k}$ is
$\frac{|L|}{p}$-close to uniform over $\mathbb{Z}_{p}^{|L|}$.

Lemma 6.3 implies the following claim:

######  Claim 2.

For every rectangle $R$ on which $\Pi^{\prime}$ outputs $w\in\\{0,1\\}^{m}$,
if $\Pr\left[\mathcal{H}_{-k}\in R_{-k}\right]\geq\frac{1}{\alpha C}$, then
for every $u\in R_{k}$ and for $\gamma,\varepsilon$ satisfying
$1-135\gamma\geq 3\varepsilon$,

$\Pr\Big{[}\mathcal{H}\in R,\;\left|F(\mathcal{H})-w\right|\leq\varepsilon
m\Big{]}<\frac{1}{2}\Pr\left[\mathcal{H}\in R\right]$ (4)

For compactness of the proof of Theorem 6.1 we defer the proofs of Claim 2 and
Lemma 6.3 to the end of this section.

Let $\widetilde{\mathcal{R}}$ be the set of the $C$ rectangles and
$\mathcal{R}\subseteq\widetilde{\mathcal{R}}$ be the set of all large
rectangles satisfying $\Pr[\mathcal{H}_{-k}\in R_{-k}]\geq\frac{1}{\alpha
C}>\frac{1}{\alpha k^{\gamma mk}}$. Then for every rectangle
$R\in\widetilde{\mathcal{R}}\backslash\mathcal{R}$,

$\Pr[\mathcal{H}\in R]\leq\Pr[\mathcal{H}_{-k}\in R_{-k}]<\frac{1}{\alpha
C}\leq\frac{1}{\alpha\big{|}\widetilde{\mathcal{R}}\backslash\mathcal{R}\big{|}}$

Using Claim 2, we have

$\displaystyle\Pr_{X\sim\mathcal{H}}\left[\left|\Pi^{\prime}_{out}(X)-F(X)\right|\leq\varepsilon
m\right]$ $\displaystyle=$
$\displaystyle\sum_{R\in\widetilde{\mathcal{R}}}\Pr\left[\mathcal{H}\in
R,\;\left|F(\mathcal{H})-\Pi^{\prime}_{out}(R)\right|\leq\varepsilon m\right]$
$\displaystyle\leq$
$\displaystyle\sum_{R\in{\mathcal{R}}}\Pr\left[\mathcal{H}\in
R,\;\left|F(\mathcal{H})-\Pi^{\prime}_{out}(R)\right|\leq\varepsilon
m\right]+\sum_{R\in\widetilde{\mathcal{R}}\backslash\mathcal{R}}\Pr[\mathcal{H}\in
R]$ $\displaystyle\leq$
$\displaystyle\sum_{R\in{\mathcal{R}}}\frac{1}{2}\Pr\left[\mathcal{H}\in
R\right]+\sum_{R\in\widetilde{\mathcal{R}}\backslash\mathcal{R}}\Pr[\mathcal{H}\in
R]$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{R\in\widetilde{\mathcal{R}}}\Pr[\mathcal{H}\in
R]+\frac{1}{2}\cdot\left|\widetilde{\mathcal{R}}\backslash\mathcal{R}\right|\cdot\frac{1}{\alpha\big{|}\widetilde{\mathcal{R}}\backslash\mathcal{R}\big{|}}\leq\frac{1}{2}+\frac{1}{2\alpha}$

Combining it with (3), we have

$1-\frac{\delta}{\varepsilon}\leq\Pr_{X\sim\mathcal{H}}\left[\left|\Pi^{\prime}_{out}(X)-F(X)\right|\leq\varepsilon
m\right]\leq\frac{1}{2}+\frac{1}{2\alpha}\implies
1-\frac{2\delta}{\varepsilon}\leq\frac{1}{\alpha}$

However, the above inequality cannot be true if we set $\varepsilon=3\delta$
and pick a constant $\alpha>3$. Let $\gamma:=(1-9\delta)/135$ be the constant
for which we want to show $c\geq\gamma mk\log k={\Omega\left({mk\log
k}\right)}$. Then $1-135\gamma=9\delta\geq 3\varepsilon$ satisfies the
condition in 2 and $\alpha={{O}\left({1}\right)}$ satisfies the requirement in
Lemma 6.3.

Thus we finish the contradiction argument and complete the proof of Theorem
6.1 with $\mathbf{RCC}_{k,\delta}(F)\geq\gamma mk\log k={\Omega\left({mk\log
k}\right)}$.

######  Proof 6.4 (Proof of Claim 2).

Recall that $G^{\prime}:=G_{k}^{(L)}\;|\;G_{-k}^{m}\in R_{-k}$, $G^{\prime}$
is $|L|/p$ close to the uniform distribution by Lemma 6.3. Therefore for every
fixed $u\in\mathbb{Z}_{p}^{|L|}$,

$\displaystyle\sum_{v\in\\{0,1\\}^{|L|}:|v|\leq\varepsilon
m}\Pr\left[G^{\prime}=u-v\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\sum_{v:|v|\leq\varepsilon
m}\Pr\left[G^{\prime}=u-v\right]+\sum_{v:|v|\geq|L|-\varepsilon
m}\Pr\left[G^{\prime}=u-\overline{v}\right]\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\left(\sum_{v:|v|\leq\varepsilon
m}\Pr\left[G^{\prime}=u-v\right]+\sum_{v:|v|\geq|L|-\varepsilon
m}\Pr\left[G^{\prime}={u-v}\right]+\frac{2|L|}{p}\right)$ $\displaystyle<$
$\displaystyle\frac{1}{2}\sum_{v\in\\{0,1\\}^{|L|}}\Pr\left[G^{\prime}={u-v}\right]$

where the first inequality follows Lemma 6.3, and the last inequality holds
since as long as $G^{\prime}$ is close to the uniform distribution and
$|L|=(1-135\gamma)m\geq 3\varepsilon m$, there is

$\sum_{v:\varepsilon m<|v|<|L|-\varepsilon
m}\Pr\left[G^{\prime}={u-v}\right]={\Omega\left({1}\right)}>\frac{|L|}{p}$

We then apply the above inequality and get

$\displaystyle\sum_{v\in\\{0,1\\}^{m}:\left|v-w\right|\leq\varepsilon
m}\Pr\left[G^{m}_{k}=u-v\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle\leq$
$\displaystyle\sum_{v\in\\{0,1\\}^{m}:\left|v_{L}-w_{L}\right|\leq\varepsilon
m}\Pr\left[G^{m}_{k}=u-v\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle=$
$\displaystyle\sum_{v_{L}\in\\{0,1\\}^{|L|}:\left|v_{L}-w_{L}\right|\leq\varepsilon
m}\Pr\left[G^{(L)}_{k}=u_{L}-v_{L}\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle\qquad\cdot\sum_{v_{-L}\in\\{0,1\\}^{m-|L|}}\Pr\left[G^{(-L)}_{k}=u_{-L}-v_{-L}\;\Big{|}\;G^{m}_{-k}\in
R_{-k},G^{(L)}_{k}=u_{L}-v_{L}\right]$ $\displaystyle<$
$\displaystyle\frac{1}{2}\sum_{v_{L}\in\\{0,1\\}^{|L|}}\Pr\left[G^{(L)}_{k}=u_{L}-v_{L}\;\Big{|}\;G^{m}_{-k}\in
R_{-k}\right]$
$\displaystyle\qquad\cdot\sum_{v_{-L}\in\\{0,1\\}^{m-|L|}}\Pr\left[G^{(-L)}_{k}=u_{-L}-v_{-L}\;\Big{|}\;G^{m}_{-k}\in
R_{-k},G^{(L)}_{k}=u_{L}-v_{L}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{v\in\\{0,1\\}^{m}}\Pr\left[G^{m}_{k}=u-v\;\Big{|}\;G^{m}_{-k}\in
R_{-k}\right]$ (5)

The above inequality (5) implies (4) since:

$\displaystyle\Pr\left[\mathcal{H}\in
R,\left|F(\mathcal{H})-w\right|\leq\varepsilon m\right]$ $\displaystyle=$
$\displaystyle\Pr\left[\mathcal{H}_{-k}\in
R_{-k}\right]\cdot\Pr\left[\mathcal{H}_{k}\in
R_{k},\left|F(\mathcal{H})-w\right|\leq\varepsilon
m\;\Big{|}\;\mathcal{H}_{-k}\in R_{-k}\right]$ $\displaystyle=$
$\displaystyle\Pr\left[G^{m}_{-k}\in
R_{-k}\right]\cdot\sum_{v\in\\{0,1\\}^{m}}\frac{1}{2^{m}}\Pr\left[\mathcal{H}_{k}\in
R_{k},\left|F(\mathcal{H})-w\right|\leq\varepsilon m\;\Big{|}\;G^{m}_{-k}\in
R_{-k},F(\mathcal{H})=v\right]$ $\displaystyle=$
$\displaystyle\Pr\left[G^{m}_{-k}\in
R_{-k}\right]\cdot\sum_{v\in\\{0,1\\}^{m}}\frac{1}{2^{m}}\Pr\left[v+G^{m}_{k}\in
R_{k},\left|v-w\right|\leq\varepsilon m\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle=$ $\displaystyle\Pr\left[G^{m}_{-k}\in
R_{-k}\right]\cdot\sum_{v\in\\{0,1\\}^{m}:\left|v-w\right|\leq\varepsilon
m}\frac{1}{2^{m}}\sum_{u\in
R_{k}}\Pr\left[v+G^{m}_{k}=u\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle=$ $\displaystyle\frac{1}{2^{m}}\Pr\left[G^{m}_{-k}\in
R_{-k}\right]\cdot\sum_{u\in
R_{k}}\sum_{v\in\\{0,1\\}^{m}:\left|v-w\right|\leq\varepsilon
m}\Pr\left[v+G^{m}_{k}=u\;\Big{|}\;G^{m}_{-k}\in R_{-k}\right]$
$\displaystyle<$ $\displaystyle\frac{1}{2^{m}}\Pr\left[G^{m}_{-k}\in
R_{-k}\right]\cdot\sum_{u\in
R_{k}}\frac{1}{2}\sum_{v\in\\{0,1\\}^{m}}\Pr\left[v+G^{m}_{k}=u\;\Big{|}\;G^{m}_{-k}\in
R_{-k}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\Pr\left[\mathcal{H}\in R\right]$

Thus we complete the proof of Claim 2

######  Proof 6.5 (Proof of Lemma 6.3).

We prove this lemma inductively for the indices in $L$. More specifically,
given that
$\left(G_{k}^{(1)},\dots,G_{k}^{(\ell-1)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is $\delta_{\ell-1}$-close to the uniform distribution over
$\mathbb{Z}_{p}^{\ell-1}$, we will show that there exists another instance
which, w.l.o.g., we label as $G_{k}^{(\ell)}$, for which
$\left(G_{k}^{(1)},\dots,G_{k}^{(\ell-1)},G_{k}^{(\ell)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is $\delta_{\ell}$-close to uniform distribution over
$\mathbb{Z}_{p}^{\ell}$. Here the statistical error bound
$\delta_{i}:=\frac{i}{p}$ for every $i\in[\ell]$.

The base case for $\ell=0$ is trivial. In what follows we suppose that the
conditional distribution
$\left(G_{k}^{(1)},\dots,G_{k}^{(\ell-1)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is already $\delta_{\ell-1}$-uniform and we do our induction for
$G_{k}^{(\ell)}$.

First we fix $x\in\mathbb{Z}_{p}^{(\ell-1)\times(k-1)}$ for which
$\Pr\left[\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)=x\;|\;G_{-k}^{m}\in
R_{-k}\right]\geq\frac{1}{\eta p^{(\ell-1)(k-1)}}$, and let $\mathcal{E}_{x}$
denote the event $\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)=x$. Then
we discuss the conditional distribution of the remaining instances given
$\mathcal{E}_{x}$.

Let $J_{x}:={\left\\{{j\in[k-1]\;\Big{|}\;\Pr\left[G^{m}_{j}\in
R_{j}\;\big{|}\;\mathcal{E}_{x}\right]\geq{1}/{\beta
k^{\gamma^{\prime}m}}}\right\\}}$. Then

$\displaystyle\Pr\left[G^{m}_{-k}\in
R_{-k}\;|\;\mathcal{E}_{x}\right]=\prod_{j\in[k-1]}\Pr\left[G_{j}^{m}\in
R_{j}\;|\;\mathcal{E}_{x}\right]\leq\prod_{j\in([k-1]\backslash
J_{x})}\frac{1}{\beta k^{\gamma^{\prime}m}}=\left(\frac{1}{\beta
k^{\gamma^{\prime}m}}\right)^{k-1-|J_{x}|}$ (6)

On the other hand, recalling that
$\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)$ is uniformly distributed
and hence $\Pr[\mathcal{E}_{x}]=\frac{1}{p^{(\ell-1)(k-1)}}$, we have

$\displaystyle\Pr\left[G^{m}_{-k}\in R_{-k}\;|\;\mathcal{E}_{x}\right]$
$\displaystyle=$ $\displaystyle\Pr\left[G^{m}_{-k}\in
R_{-k},\mathcal{E}_{x}\right]/\Pr[\mathcal{E}_{x}]$ $\displaystyle=$
$\displaystyle\Pr\left[\mathcal{E}_{x}\;\Big{|}\;G_{-k}^{m}\in
R_{-k}\right]\cdot\Pr[G_{-k}^{m}\in R_{-k}]/\Pr[\mathcal{E}_{x}]$
$\displaystyle\geq$ $\displaystyle\frac{1}{\eta
p^{(\ell-1)(k-1)}}\cdot\frac{1}{\alpha k^{\gamma
mk}}\Big{/}\left(\frac{1}{p^{(\ell-1)(k-1)}}\right)=\frac{1}{\eta\alpha
k^{\gamma mk}}$ (7)

Combining Equations 6 and 7 and letting
$\beta\geq(\eta\alpha)^{{\gamma^{\prime}}/{\gamma k}}$, we can conclude

$\left(\frac{1}{\beta
k^{\gamma^{\prime}m}}\right)^{k-1-|J_{x}|}\geq\frac{1}{\eta\alpha k^{\gamma
mk}}\implies|J_{x}|\geq k-1-\frac{\gamma mk\log
k+\log\eta\alpha}{\gamma^{\prime}m\log
k+\log\beta}\geq\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1$

Thus the size of $J_{x}$ is at least
$|J_{x}|\geq\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1={\Omega\left({k}\right)}$.

For every $j\in J_{x}$, we have $\Pr\left[G^{m}_{j}\in
R_{j}\;\big{|}\;\mathcal{E}_{x}\right]\geq{1}/{\beta k^{\gamma^{\prime}m}}$ by
definition of $J_{x}$ and hence

$\displaystyle\mathsf{H}\left[G^{m}_{j}\;|\;G^{m}_{j}\in
R_{j},\mathcal{E}_{x}\right]\geq\log\left({p^{m-\ell}}/{\beta
k^{\gamma^{\prime}m}}\right)=(m-\ell)\log p-\gamma^{\prime}m\log k-\log\beta$
(8)

Note that for every $i\in[m]$, $G_{j}^{(i)}$ is uniform over $\mathbb{Z}_{p}$
as long as $j\in[k-1]$. Thus conditioned on $\mathcal{E}_{x}$ and
$G_{j}^{m}\in R_{j}$, if $\exists a\in\mathbb{Z}_{p}$,
$\Pr[G_{j}^{(i)}=a\;|\;G_{j}^{m}\in R_{j},\mathcal{E}_{x}]=p_{a}>\frac{1}{2}$
then we have an upper bound for the conditional entropy of $G_{j}^{(i)}$:

$\displaystyle\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}]\leq
p_{a}\log\frac{1}{p_{a}}+(1-p_{a})\log(p-1)<(1+\log(p-1))/2$

Let $I_{j,x}$ be defined as

$I_{j,x}:={\left\\{{i\in[m]\;|\;\mathsf{H}_{\infty}\left[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}\right]\geq 1}\right\\}}={\left\\{{i\;|\;\forall
a,\Pr\left[G_{j}^{(i)}=a\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}\right]\leq\frac{1}{2}}\right\\}}$

Then $\forall i\in\overline{I_{j,x}}:=\left(([m]\backslash[\ell-1])\backslash
I_{j,x}\right)$, $\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}]<(1+\log(p-1))/2$, and in particular for $i\in[\ell-1]$
we have $\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in R_{j},\mathcal{E}_{x}]=0$
since it is already fixed in $\mathcal{E}_{x}$.

$\displaystyle\mathsf{H}\left[G^{m}_{j}\;|\;G^{m}_{j}\in
R_{j},\mathcal{E}_{x}\right]\leq$
$\displaystyle\sum_{i=1}^{m}\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}]$ $\displaystyle=$ $\displaystyle\sum_{i\in
I_{j,x}}\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}]+\sum_{i\in\overline{I_{j,x}}}\mathsf{H}[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}]$ $\displaystyle\leq$ $\displaystyle|I_{j,x}|\cdot\log
p+(m-\ell+1-|I_{j,x}|)(1+\log(p-1))/2$

Combining the above with the lower bound for
$\mathsf{H}\left[G^{m}_{j}\;|\;G^{m}_{j}\in R_{j},\mathcal{E}_{x}\right]$ in
(8),

$\displaystyle(m-\ell)\log p-\gamma^{\prime}m\log k-\log\beta$
$\displaystyle\leq|I_{j,x}|\cdot\log p+(m-\ell+1-|I_{j,x}|)(1+\log(p))/2$
$\displaystyle\implies\left(\frac{\log p-1}{2}\right)|I_{j,x}|$
$\displaystyle\geq(m-\ell)\left(\frac{\log p-1}{2}\right)-\gamma^{\prime}m\log
k-\frac{1+\log p}{2}-\log\beta$

Therefore, recalling that $p>k^{1/4}$ and for $\log\beta=o(\log p)=o(\log k)$,
we have

$|I_{j,x}|\geq m-\ell-\frac{2\gamma^{\prime}m\log k}{\log
p-1}-{{O}\left({\frac{\log\beta}{\log
p}}\right)}>m-\ell-\frac{2\gamma^{\prime}m\log k}{\frac{1}{4}\log
k-1}-{o\left({1}\right)}>m-\ell-9\gamma^{\prime}m+1$

Now for every $x\in\mathbb{Z}_{p}^{(\ell-1)\times(k-1)}$ for which
$\Pr\left[\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)=x\;|\;G_{-k}^{m}\in
R_{-k}\right]\geq\frac{1}{\eta p^{(\ell-1)(k-1)}}$, the size of
$|J_{x}|\geq\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1={\Omega\left({k}\right)}$;
and for every $j\in J_{x}$, $|I_{j,x}|>m-\ell-9\gamma^{\prime}m+1$ and
$\left|\overline{I_{j,x}}\right|=m-\ell+1-|I_{j,x}|<9\gamma^{\prime}m$. That
is, the above statement holds with probability at least $1-\frac{1}{\eta}$ for
$x\sim\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$. In what follows we abuse notation a little by assuming
$\mathcal{X}:=\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is a distribution over $\mathbb{Z}_{p}^{(\ell-1)(k-1)}$ for which
$\mathcal{X}$ satisfies all the above statements of $J_{x}$ and $I_{j,x}$.
This causes at most an additional loss of $\frac{1}{\eta}$ in the error
probability.

Notice that the conditional distribution
$\left(G_{-k}^{(1)},\dots,G_{-k}^{(\ell-1)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is indeed a product distribution since $R$ is a rectangle. That is,
letting $x=(x_{1},\dots,x_{k-1})$ where $x_{j}\in\mathbb{Z}_{p}^{\ell-1}$ for
$j\in[k-1]$, then $\mathcal{E}_{x}$ can be decomposed into $k-1$ independent
events $\mathcal{E}_{x_{j}}$, where each $\mathcal{E}_{x_{j}}$ denotes the
event $\left(G_{j}^{(1)},\dots,G_{j}^{(\ell-1)}\right)=x_{j}$ and
$\mathcal{E}_{x}=\wedge_{j=1}^{k-1}\mathcal{E}_{x_{j}}$. Therefore the
conditional distribution $G^{m}_{j}\;\big{|}\;\mathcal{E}_{x}$ is identical to
$G_{j}^{m}\;\Big{|}\;\mathcal{E}_{x_{j}}$ since the distribution of
$G^{m}_{j}$ is independent from inputs of the remaining $k-2$ players (among
the first $k-1$ players) in the product distribution. As a result, we have
$\Pr\left[G^{m}_{j}\in
R_{j}\;\big{|}\;\mathcal{E}_{x}\right]=\Pr\left[G_{j}^{m}\in
R_{j}\;\Big{|}\;\mathcal{E}_{x_{j}}\right]$ so that $\mathcal{E}_{x_{j}}$ and
$x_{j}$ fully determines whether $j\in J_{x}$ following the definition of
$J_{x}$. Similarly we have $G_{j}^{(i)}\;\Big{|}\;{\left\\{{G_{j}^{m}\in
R_{j},\mathcal{E}_{x}}\right\\}}$ identical to
$G_{j}^{(i)}\;\Big{|}\;{\left\\{{G_{j}^{m}\in
R_{j},\mathcal{E}_{x_{j}}}\right\\}}$, so that $I_{j,x}$ is also fully
determined by $x_{j}$ and $\mathcal{E}_{x_{j}}$.

Next we fix $j\in[k-1]$ and pick $x_{j}\in\mathbb{Z}_{p}^{\ell-1}$ for which
$j\in J_{x}$ for $x$ extended from $x_{j}$. Now we have $\mathcal{E}_{x_{j}}$
and $I_{j,x_{j}}:=I_{j,x}$ containing all but a fraction of
$<\frac{9\gamma^{\prime}m}{m-\ell+1}$ coordinates, since
$\left|\overline{I_{j,x_{j}}}\right|<9\gamma^{\prime}m$ out of the $m-\ell+1$
unfixed coordinates in total. Then for
$X_{j}\sim\mathcal{U}_{\mathbb{Z}_{p}^{\ell-1}}$ and $\mathcal{I}(\cdot)$
denoting the indicator function,

$\displaystyle\sum_{i=\ell}^{m}\mathcal{I}\left(\Pr_{X_{j}}\left[i\in\overline{I_{j,X_{j}}}\;\Big{|}\;j\in
J_{X_{j}}\right]\geq\frac{1}{3}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{i=\ell}^{m}3\Pr_{X_{j}}\left[i\in\overline{I_{j,X_{j}}}\;\Big{|}\;j\in
J_{X_{j}}\right]$ $\displaystyle=$ $\displaystyle
3\sum_{i=\ell}^{m}\sum_{x_{j}\in\mathbb{Z}_{p}^{\ell-1}:j\in
J_{x_{j}}}\Pr[X_{j}={x_{j}}]\cdot\mathcal{I}\left(i\in\overline{I_{j,x_{j}}}\right)$
$\displaystyle=$ $\displaystyle 3\sum_{x_{j}\in\mathbb{Z}_{p}^{\ell-1}:j\in
J_{x_{j}}}\Pr[X_{j}={x_{j}}\;|\;j\in
J_{X_{j}}]\cdot\sum_{i=\ell}^{m}\mathcal{I}\left(i\in\overline{I_{j,x_{j}}}\right)$
$\displaystyle=$ $\displaystyle 3\sum_{x_{j}\in\mathbb{Z}_{p}^{\ell-1}:j\in
J_{x_{j}}}\Pr[X_{j}={x_{j}}\;|\;j\in
J_{X_{j}}]\cdot\left|\overline{I_{j,x_{j}}}\right|<27\gamma^{\prime}m$

That is, for every fixed $j\in[k-1]$, there are at least
$m-\ell+1-27\gamma^{\prime}m$ coordinates $i\in[m]$ satisfying $\Pr\left[i\in
I_{j,X_{j}}\;\Big{|}\;j\in J_{X_{j}}\right]>\frac{2}{3}$, i.e., with
probability $\frac{2}{3}$, $G_{j}^{(i)}$ satisfies
$\mathsf{H}_{\infty}\left[G_{j}^{(i)}\;|\;G_{j}^{m}\in
R_{j},\mathcal{E}_{x}\right]\geq 1$ for a randomly selected $x_{j}$
conditioned on that $j\in J_{x_{j}}$ specifies a big component in the
rectangle. This is exactly the probability that the $i$-th coordinate
$G_{j}^{(i)}$ of $G_{j}^{m}$ can be decomposed into a convex combination of a
uniform distribution over $2$ elements.

Now we have at least $(m-\ell+1-27\gamma^{\prime}m)(k-1)$ pairs of
$(i,j)\in{\left\\{{\ell,\ell+1,\dots,m}\right\\}}\times[k-1]$ satisfying the
above condition $\Pr\left[i\in I_{j,X_{j}}\;\Big{|}\;j\in
J_{X_{j}}\right]>\frac{2}{3}$, which means at least one fixed $i$ must appear
in
$\frac{(m-\ell+1-27\gamma^{\prime}m)(k-1)}{m-\ell+1}=\left(1-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)(k-1)$
many pairs for different $j\in[k-1]$ by a standard averaging argument. Without
loss of generality we may assume $i=\ell$, and let
$G^{\prime\prime}:=(G^{\prime\prime}_{1},\dots,G^{\prime\prime}_{k})$ denote
the conditional distribution of $G^{(\ell)}$, i.e., each
$G_{j}^{\prime\prime}:=G_{j}^{(\ell)}\;\Big{|}\;{\left\\{{G_{j}^{m}\in
R_{j},\mathcal{E}_{x}}\right\\}}$ denotes the conditional distribution of
$G_{j}^{(\ell)}$. Recalling that
$|J_{x}|\geq\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1$, the number of
elements in $|J_{x}|$ hit by those pairs containing $\ell$ is at least

$\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1+\left(1-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)(k-1)-(k-1)\geq\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k-1={\Omega\left({k}\right)}$

We say the pair $(i,j)$ is _good for $x$_ if $j\in J_{x}$ and $i\in I_{j,x}$.
Then recalling that
$|J_{x}|\geq\left(1-\frac{\gamma}{\gamma^{\prime}}\right)k-1$, the expected
number of good $(\ell,j)$ over $x\sim\mathcal{X}$ is lower bounded as follows.

$\displaystyle\mathbf{E}_{x}\left[\\#{\left\\{{j\in[k-1]\;|\;\text{$(\ell,j)$
is good for $x$}}\right\\}}\right]$ $\displaystyle=$
$\displaystyle\mathbf{E}_{x}\left[\sum_{j=1}^{k-1}\mathcal{I}\left(\text{$(\ell,j)$
is good for $x$}\right)\right]$ $\displaystyle\geq$
$\displaystyle\mathbf{E}_{x}\left[\sum_{j=1}^{k-1}\mathbf{E}_{x}\left[\mathcal{I}\left(\text{$(\ell,j)$
is good for
$x$}\right)\right]\right]=\mathbf{E}_{x}\left[\sum_{j=1}^{k-1}\Pr_{x}[\ell\in
I_{j,x},j\in J_{x}]\right]$ $\displaystyle\geq$
$\displaystyle\mathbf{E}_{x}\left[\sum_{j\in J_{x}}\Pr_{x}[\ell\in
I_{j,x}\;|\;j\in J_{x}]\right]$ $\displaystyle\geq$
$\displaystyle\frac{2}{3}\cdot\left(\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k-1\right)$

By a Chernoff bound it implies

$\displaystyle\Pr_{x}\left[\\#{\left\\{{j\in[k-1]\;|\;\text{$(\ell,j)$ is good
for
$x$}}\right\\}}\leq\frac{1}{3}\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k\right]$
$\displaystyle\leq$
$\displaystyle\exp\left(-{\Omega\left({\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k}\right)}\right)$

Let
$\delta^{\prime}=\exp\left(-{\Omega\left({\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k}\right)}\right)$
be an upper bound of this error probability. Then with probability at least
$1-\delta^{\prime}$, the conditional distribution $G_{j}^{\prime\prime}$ can
be decomposed into a convex combination of uniform distributions over two
distinct elements for at least
$\frac{1}{3}\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k$
indices $j\in[k-1]$.

Next we show that conditioned on the above decomposition, which happens with
probability $\geq 1-\delta^{\prime}$, the conditional distribution
$G^{\prime\prime}_{k}$ is close to uniform by the following claim.

######  Claim 3 (Claim 31 in [19]).

Let $p$ be a prime number. Let $X$ be the sum of $t$ independent random
variables each uniform over
${\left\\{{a_{i},b_{i}}\right\\}}\subset\mathbb{Z}_{p}$ for $a_{i}\neq b_{i}$.
Then $X$ modulo $p$ is $\delta\leq
0.5\sqrt{p}\exp\left(-{\Omega\left({t/p^{2}}\right)}\right)$ close to uniform.

Plugging our parameters into the above claim and following exactly the same
argument as in [19] ($G_{k}^{\prime\prime}$ is $\delta^{\prime\prime}$-close
to uniform if every component in the above convex decomposition of
$G_{k}^{\prime\prime}$ is $\delta^{\prime\prime}$-close to uniform), the
statistical distance between
$G_{k}^{\prime\prime}=-\sum_{j=1}^{k-1}G_{j}^{\prime\prime}$ and the uniform
distribution over $\mathbb{Z}_{p}$ is bounded by

$\displaystyle\delta^{\prime\prime}\leq$ $\displaystyle
0.5\sqrt{p}\exp\left(-{\Omega\left({\frac{1}{3}\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)k/p^{2}}\right)}\right)$
$\displaystyle=$
$\displaystyle\exp\left(-{\Omega\left({\left(1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\right)\sqrt{k}}\right)}\right)$

Putting it all together, we conclude that
$G_{k}^{(\ell)}\;\Big{|}\;{\left\\{{G_{-k}^{m}\in
R_{-k},G^{(1)},\dots,G^{(\ell-1)}}\right\\}}$ is close to uniform, which
implies
$\left(G_{k}^{(1)},\dots,G_{k}^{(\ell-1)},G_{k}^{(\ell)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is also close to uniform. Moreover, its statistical distance to
uniform is bounded by

$\displaystyle\delta_{\ell}\leq\delta_{\ell-1}+\frac{1}{\eta}+\delta^{\prime}+\delta^{\prime\prime}$

Let $\gamma^{\prime}=2\gamma$, $\eta=2p$ and
$\beta=2\geq(\eta\alpha)^{\gamma^{\prime}/\gamma k}=2^{{{O}\left({\frac{\log
k}{k}}\right)}}$ for $\alpha=p^{{O}\left({1}\right)}$. Then for sufficiently
large $k$m the above induction argument goes through for
$\ell\leq(1-135\gamma)m$, with error $\delta^{\prime},\delta^{\prime\prime}$
bounded by

$\delta^{\prime}=\exp\left(-{\Omega\left({{k}}\right)}\right),\delta^{\prime\prime}=\exp\left(-{\Omega\left({\sqrt{k}}\right)}\right)\Longleftarrow
1-\frac{\gamma}{\gamma^{\prime}}-\frac{27\gamma^{\prime}m}{m-\ell+1}\geq
0.1\Longleftrightarrow\ell\leq(1-135\gamma)m+1$

Therefore the conditional distribution
$\left(G_{k}^{(1)},\dots,G_{k}^{(\ell-1)},G_{k}^{(\ell)}\right)\;\Big{|}\;G_{-k}^{m}\in
R_{-k}$ is $\delta_{\ell}$-close to uniform for $\delta_{\ell}$ bounded by
$\frac{\ell}{p}$ as follows:

$\delta_{\ell}\leq\delta_{\ell-1}+\frac{1}{\eta}+\delta^{\prime}+\delta^{\prime\prime}\leq\frac{\ell-1}{p}+\frac{1}{2p}+\exp\left(-{\Omega\left({\sqrt{k}}\right)}\right)\leq\frac{\ell}{p}$

Thus we have proved the induction hypothesis for every
$\ell\leq(1-135\gamma)m$. Let $L$ be the first $(1-135\gamma)m$ indices as in
the induction hypothesis, we complete the proof of Lemma 6.3 for
$|L|=(1-135\gamma)m$ and statistical distance $\frac{|L|}{p}$.

##  7 Lower bound for Hamming Norm Estimation

In this section we present a space lower bound for single-pass streaming
algorithms for $(1\pm\varepsilon)$-approximating the Hamming norm $L_{0}$ in
the strict turnstile model, which is denoted by $\textsc{T}_{\varepsilon}$ as
in Section 1.1.1.

Formally, in the Hamming norm estimation problem there is an underlying vector
$(x_{1},\dots,x_{N})$ which starts from the all zero vector and processes up
to $m$ updates each of the form $(i,v)\in[N]\times[\pm M]$. The update $(i,v)$
means one should add $v$ to the $i$-th coordinate $x_{i}$ in the vector $x$.
After processing all $m$ updates, we have
${\left\|{x}\right\|}_{0}=|{\left\\{{i\;|\;x_{i}\neq 0}\right\\}}|$ and we
want to output a number within $(1\pm\varepsilon)\|x\|_{0}$ with probability
$\geq 2/3$. The strict turnstile model guarantees that $x_{i}\geq 0$ for all
$i\in[N]$ at all positions in the stream, in which case it suffices to prove
the space lower bound in the simultaneous communication model following the
reduction in Theorem 4.1 of [2]. Furthermore, it is also guaranteed that for
every $i\in[N]$, $x_{i}\leq\mathsf{poly}(n)$ at the end of the stream. In this
setting, the algorithm of [13] approximates $\|x\|_{0}$ up to a
$(1\pm\varepsilon)$ factor with
${{O}\left({\varepsilon^{-2}\log(N)\left(\log(1/\varepsilon)+\log\log(mM)\right)}\right)}$
bits of space222Indeed, their algorithm stores
${{O}\left({\varepsilon^{-2}\log N}\right)}$ counters modulo primes that are
each ${{O}\left({\log(1/\varepsilon)+\log\log(mM)}\right)}$ bits in magnitude,
and it does not matter how large the values of $x_{i}$ are at intermediate
positions in the stream. , as long as $\varepsilon>0$.

######  Theorem 7.1.

For error tolerance $\varepsilon<1/3$ and
$\varepsilon=\max{\left\\{{{\Omega\left({\sqrt{\frac{\log
k}{k}}}\right)},\frac{1}{{N}^{0.49}}}\right\\}}$, any single-pass streaming
algorithm solving $\textsc{T}_{\varepsilon}$ with probability $\geq 2/3$ in
the strict turnstile model must use
${\Omega\left({\varepsilon^{-2}\log(N)\log\log(mM)}\right)}$ bits of space.

######  Proof 7.2.

First we introduce the $\varepsilon$-$\textsc{Gap-Hamming-of-Sum-Equal}_{n}$
problem, which for simplicity we denote by $\varepsilon$-$\textsc{GHSE}_{n}$.
The input of every player $j\in[k]$ is
$\mathbf{x}_{j}=\left(\mathbf{x}_{j}^{(1)},\dots,\mathbf{x}_{j}^{(n)}\right)\in\mathbb{Z}^{n}$.
Let $Z^{(i)}\in{\left\\{{\pm 1}\right\\}}$ denote the result of the $i$-th
instance of the Sum-Equal problem for every $i\in[n]$, i.e.
$Z^{(i)}:=\textsc{Sum-
Equal}_{k}\left(\mathbf{x}_{1}^{(i)},\mathbf{x}_{2}^{(i)},\dots,\mathbf{x}_{k}^{(i)}\right)$.
Let $\textsc{HSE}(\mathbf{x}):=\sum_{i=1}^{n}Z^{(i)}$ denote the bias of
$Z^{(i)}$’s on input
$\mathbf{x}=\left(\mathbf{x}_{1},\dots,\mathbf{x}_{k}\right)$. The output of
$\varepsilon$-$\textsc{GHSE}_{n}$ on input $\mathbf{x}$ is $1$ if
$\textsc{HSE}(\mathbf{x})\geq\varepsilon\sqrt{n}$, and the output is $0$ if
$\textsc{HSE}(\mathbf{x})\leq-\varepsilon\sqrt{n}$.

Then we prove the following lemmas.

######  Lemma 7.3.

For every $k\in\mathbb{Z}$, $0\leq\delta\leq 1/2$, and $n\geq
c^{2}/\varepsilon^{2}=n^{\prime}$, there is

$\overrightarrow{\mathbf{RCC}}_{k,\delta}\left(\text{$\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$}\right)\geq\overrightarrow{\mathbf{RCC}}_{k,\delta}\left(\text{$c$-$\textsc{GHSE}_{n^{\prime}}$}\right)$

######  Proof 7.4 (Proof of Lemma 7.3).

Given $n^{\prime}=c^{2}/\varepsilon^{2}$ and an input instance of
$c$-$\textsc{GHSE}_{n^{\prime}}$ with underlying Sum-Equal problems outputting
$\mathbf{x}^{\prime}\in\\{0,1\\}^{n^{\prime}}$, we create the new input to
$\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$ by taking $\varepsilon^{2}n/c^{2}$
copies of each coordinate, with results of underlying problems being
$\mathbf{x}\in{\left\\{{\pm 1}\right\\}}^{n}$. As a result,
$\sum_{j=1}^{n}\mathbf{x}_{j}=\frac{\varepsilon^{2}n}{c^{2}}\cdot\sum_{j=1}^{n^{\prime}}\mathbf{x}^{\prime}_{j}$.

If $\sum_{j}\mathbf{x}^{\prime}_{j}\geq c\sqrt{n^{\prime}}$, then
$\sum_{j}\mathbf{x}_{j}\geq\varepsilon n$, and on the other hand
$\sum_{j}\mathbf{x}^{\prime}_{j}\leq-c\sqrt{n^{\prime}}$ implies
$\sum_{j}\mathbf{x}_{j}\leq-\varepsilon n$. Thus, any $k$-player
$\delta$-error one-way protocol for $\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$
immediately implies a $k$-player $\delta$-error one-way protocol for
$c$-$\textsc{GHSE}_{n^{\prime}}$. The same argument holds in the simultaneous
communication model.

######  Lemma 7.5.

For every $n^{\prime}\in\mathbb{Z}$, there exists
$n^{\prime\prime}={\Theta\left({n^{\prime}}\right)}$, such that
$\mathbf{RCC}^{sim}_{k,0.01}\left(\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\right)={\Omega\left({n^{\prime\prime}k\log\log
k}\right)}$.

Furthermore, the lower bound holds for an input distribution $\mu$ over
$\mathbb{Z}^{n^{\prime}\times k}$, such that for $\mathbf{x}\sim\mu$, the
conditional expectations of $\textsc{HSE}(\mathbf{x})$ satisfies

$\displaystyle\mathbf{E}\left[\textsc{HSE}(\mathbf{x})\;|\;\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}(\mathbf{x})=1\right]$
$\displaystyle=10\sqrt{n^{\prime}}$
$\displaystyle\mathbf{E}\left[\textsc{HSE}(\mathbf{x})\;|\;\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}(\mathbf{x})=0\right]$
$\displaystyle=-10\sqrt{n^{\prime}}$

and $\mathbf{Var}\left(\textsc{HSE}(\mathbf{x})\right)\leq n^{\prime}$ in both
cases.

######  Proof 7.6 (Proof of Lemma 7.5).

In this proof, we first introduce the Aug-Index-Sum-Equal problem and prove
that

$\mathbf{RCC}^{sim}_{k,0.01}\left(\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\right)\geq\mathbf{RCC}^{sim}_{k,0.1}\left({\textsc{Aug-
Index-Sum-Equal}^{n^{\prime\prime}}_{k}}\right)$

and then the lower bound for $\mathbf{RCC}^{sim}_{k,0.1}\left({\textsc{Aug-
Index-Sum-
Equal}^{n^{\prime\prime}}_{k}}\right)={\Omega\left({n^{\prime\prime}k\log\log
k}\right)}$ follows Theorem 7.7.

The $\textsc{Aug-Index-Sum-Equal}_{k}^{n^{\prime\prime}}$ problem, which is
the _$k$ -player $n^{\prime\prime}$-fold augmented index of the Sum-Equal
problem_, is defined as follows:

  * •

there are $n^{\prime\prime}$ copies of $\textsc{Sum-
Equal}_{k}^{(1)},\ldots,\textsc{Sum-Equal}_{k}^{(n^{\prime\prime})}$ and $k$
players, among which the last player is the _referee_ ;

  * •

each of the $k-1$ players has inputs to the $n^{\prime\prime}$ copies of
$\textsc{Sum-Equal}_{k}$, and sends one message to the referee (let these
messages be denoted by $M_{1},\ldots,M_{k-1}$);

  * •

the referee gets an input to each of the $n^{\prime\prime}$ copies as well,
together with an index $j\in[n^{\prime\prime}]$ and the answers to
$\textsc{Sum-Equal}_{k}^{(j+1)},\ldots,\textsc{Sum-
Equal}_{k}^{(n^{\prime\prime})}$;

  * •

on receiving the other $k-1$ players’ messages, the referee outputs an
estimate to $\textsc{Sum-Equal}_{k}^{(j)}$.

Then we consider the $\textsc{Aug-Index-Sum-Equal}^{n^{\prime\prime}}_{k}$
problem in the simultaneous communication model. Let Alice simulate a non-
referee player who gets input
$X=\left(X^{(1)},\dots,X^{(n^{\prime\prime})}\right)\in\mathbb{Z}^{n^{\prime\prime}}$,
and let Bob simulate the referee together with the remaining $k-2$ non-referee
players, whose input (to the underlying $\textsc{Sum-Equal}_{k}$ instances) is
effectively
$Y=\left(Y^{(1)},\dots,Y^{(n^{\prime\prime})}\right)\in\mathbb{Z}^{n^{\prime\prime}}$.
Following the simultaneous communication protocol Alice sends a message $M$ to
Bob, and Bob decides the output based on $Y$ and $M$, where the
$n^{\prime\prime}$ copies of underlying $\textsc{Sum-Equal}_{k}$ instances
reduce to $\textsc{Sum-Equal}_{2}$ instances. In what follows we assume
$n^{\prime\prime}$ is odd and reduce the $\textsc{Aug-Index-Sum-
Equal}^{n^{\prime\prime}}_{2}$ problem to $1$-$\textsc{GHSE}_{n^{\prime}}$.

Use the CRS to select $n^{\prime}\times n^{\prime\prime}$ independent random
hash functions $h_{ij}$ from the universal family of hash functions
$H={\left\\{{h:\mathbb{Z}\to\\{0,1\\}}\right\\}}$, that is for $x\neq y$ and
$h$ uniformly drawn from $H$, $h(x)=h(y)$ w.p. $1/2$. For example, $h$ can be
represented as a binary string (possibly of infinite length) and $h(x)$ is the
inner product of the binary representations of $x$ and $h$.

Then Alice computes $r_{ij}:=h_{ij}\left(X^{(j)}\right)$ for every
$(i,j)\in[n^{\prime}]\times[n^{\prime\prime}]$ and the vector
$\mathbf{m}=(m_{1},\dots,m_{n^{\prime}})$ where for
$i\in[n^{\prime}-10\sqrt{n^{\prime}}]$,
$m_{i}:=\mathsf{MAJ}_{j\in[n^{\prime\prime}]}r_{ij}$ is the majority of hashed
values of $X$’s coordinates, and $m_{i}=0$ for other $i\in[n^{\prime}]$, i.e.,
$n^{\prime}-10\sqrt{n^{\prime}}<i\leq n^{\prime}$. Alice takes $\mathbf{m}$ as
her input in the $1$-$\textsc{GHSE}_{n^{\prime}}$ instance and composes the
message $M$ accordingly.

On receiving $M$ and given an index $j\in[n^{\prime\prime}]$, Bob determines
the output of $\textsc{Sum-Equal}_{2}^{(j)}$ as follows:

  1. 1.

Compute the vector
$\mathbf{m}^{\prime}=\left(m^{\prime}_{1},\dots,m^{\prime}_{n^{\prime}}\right)$
by letting $m^{\prime}_{i}=1-h_{ij}\left(Y^{(j)}\right)$ for every
$i\in[n^{\prime}-10\sqrt{n^{\prime}}]$, and $m^{\prime}_{i}=0$ for other
$i\in[n^{\prime}]$. That is, we pad $10\sqrt{n^{\prime}}$ copies of
$0$-instances to the input.

  2. 2.

Compute the output of
$\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\left(\mathbf{m},\mathbf{m}^{\prime}\right)$
based on $\mathbf{m}^{\prime}$ and $M$.

  3. 3.

Output exactly the same as
$\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\left(\mathbf{m},\mathbf{m}^{\prime}\right)$.

Note that if $X^{(j)}=Y^{(j)}$, then $m^{\prime}_{i}=1-r_{ij}$ for
$i\in[n^{\prime}-10\sqrt{n^{\prime}}]$ and hence

$\displaystyle\Pr\left[m^{\prime}_{i}\neq m_{i}\;|\;X^{(j)}=Y^{(j)}\right]=$
$\displaystyle\Pr\left[r_{ij}=1\right]\sum_{s=(n^{\prime\prime}-1)/2}^{n^{\prime\prime}-1}\Pr\left[\sum_{k\in[n^{\prime\prime}]\backslash{\left\\{{j}\right\\}}}r_{ik}=s\;\big{|}\;r_{ij}=1\right]$
$\displaystyle+\Pr\left[r_{ij}=0\right]\sum_{s=0}^{(n^{\prime\prime}-1)/2}\Pr\left[\sum_{k\in[n^{\prime\prime}]\backslash{\left\\{{j}\right\\}}}r_{ik}=s\;\big{|}\;r_{ij}=0\right]$
$\displaystyle=$
$\displaystyle\sum_{s=0}^{(n^{\prime\prime}-1)/2}2^{1-n^{\prime\prime}}\binom{n^{\prime\prime}-1}{s}>\frac{1}{2}+\frac{1}{2\sqrt{n^{\prime\prime}}}$

where the probability is taken over the choice of hash functions and the last
inequality follows from Stirling’s formula. Thus for sufficiently large
$n^{\prime}$, say $n^{\prime}\geq 900n^{\prime\prime}$,

$\mathbf{E}\left[\textsc{HSE}\left(\mathbf{m},\mathbf{m^{\prime}}\right)\;|\;X^{(j)}=Y^{(j)}\right]>-10\sqrt{n^{\prime}}+\frac{n^{\prime}-10\sqrt{n^{\prime}}}{\sqrt{n^{\prime\prime}}}\geq
10\sqrt{n^{\prime}}$

Notice that for every $i\in[n^{\prime}]$, the event whether
$m_{i}=m^{\prime}_{i}$ is independent from others. On the other hand, since
$m^{\prime}_{i}$’s are independent from $r_{ij}$’s for randomly chosen hash
functions, $\mathbf{m}$ is independent from $\mathbf{m^{\prime}}$ and hence
$\mathbf{E}\left[\textsc{HSE}\left(\mathbf{m},\mathbf{m^{\prime}}\right)\;|\;X^{(j)}\neq
Y^{(j)}\right]=-10\sqrt{n^{\prime}}$. Furthermore, because of the independence
of $m^{\prime}_{i}$’s, the variance of
$\textsc{HSE}\left(\mathbf{m},\mathbf{m^{\prime}}\right)$ is bounded by
$n^{\prime}$ in both cases. Hence in both cases

$\Pr\left[\Big{|}\textsc{HSE}\left(\mathbf{m},\mathbf{m^{\prime}}\right)-\mathbf{E}\left[\textsc{HSE}\left(\mathbf{m},\mathbf{m^{\prime}}\right)\right]\Big{|}\geq
9\sqrt{n^{\prime}}\right]\leq\frac{n^{\prime}}{\left(9\sqrt{n^{\prime}}\right)^{2}}=1/81$

As a result,
$\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\left(\mathbf{m},\mathbf{m}^{\prime}\right)$
outputs $1$ with probability $\geq 0.95$ when $X^{(j)}=Y^{(j)}$, and it
outputs $0$ with probability $\geq 0.95$ when $X^{(j)}\neq Y^{(j)}$.

Therefore by repeating the above procedure for every $j$ and taking into
consideration the error probability of solving the
$1$-$\textsc{GHSE}_{n^{\prime}}$ problem, Bob solves $\textsc{Sum-
Equal}_{2}^{(j)}$ for every index $j$ with probability $\geq 0.9$. That is,

$\mathbf{RCC}^{sim}_{k,0.01}\left(\text{$1$-$\textsc{GHSE}_{n^{\prime}}$}\right)\geq\mathbf{RCC}^{sim}_{k,0.1}\left({\textsc{Aug-
Index-Sum-Equal}^{n^{\prime\prime}}_{k}}\right)$

The above inequality holds in the CRS model. However, the CRS can be removed
with only a logarithmic additive loss using Newman’s Theorem [17, 16].

The ${\Omega\left({n^{\prime\prime}k\log\log k}\right)}$ lower bound of
$k$-player $0.1$-error simultaneous communication complexity of $\textsc{Aug-
Index-Sum-Equal}^{n^{\prime\prime}}_{k}$ follows Theorem 7.7, as proved in
Appendix B.

######  Theorem 7.7.

Let $\Pi$ be an $\delta$-error randomized simultaneous $k$-player protocol
that solves $\textsc{Aug-Index-Sum-Equal}_{k}^{m}$, where $m\leq 0.1\log k$
and the error tolerance $\delta\in(0,1/6)$. The simultaneous communication
cost of $\Pi$ is $\mathbf{RCC}^{sim}_{k,\delta}(\Pi)={\Omega\left({mk\log\log
k}\right)}$.

Furthermore, the lower bound holds when the inputs to the $\textsc{Sum-
Equal}_{k}$ problems are drawn from $\left([a]^{m}\right)^{k-1}\times[\pm
ka]^{m}$ and the sum of inputs to each copy of $\textsc{Sum-Equal}_{k}$ is
promised to be $0$ or $q$, where $a={{O}\left({\log k}\right)}$ and
$q=2^{{{O}\left({a}\right)}}\leq k^{1/8}$ is a multiple of all integers in
$[a]$.

Thus we finish the proof of Lemma 7.5.

Combining Lemma 7.3, Lemma 7.5, and Theorem 4.1 of [2], we get the following
corollary for $\varepsilon={\Omega\left({1/\sqrt{n}}\right)}$:

######  Corollary 7.8.

For every $k\in\mathbb{Z}$, $\delta<1/3$, constant $\varepsilon$ and
$n={\Omega\left({1/\varepsilon^{2}}\right)}$, there is

$\mathbf{RCC}^{sim}_{k,\delta}\left(\text{$\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$}\right)={\Omega\left({\varepsilon^{-2}k\log\log
k}\right)}$

Next we introduce the $\textsc{Aug-Index-GHSE}_{n,k}^{t}$ problem and reduce
it to the Hamming estimation problem $\textsc{T}_{\varepsilon}$.

Similar to the definition of Aug-Index-Sum-Equal , the $\textsc{Aug-Index-
GHSE}_{n,k}^{t}$ problem has $t={\Theta\left({\log n}\right)}$ instances of
the $\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$ problem embedded into it,
denoted by $g_{1},\dots,g_{t}$. Each of the first $k-1$ players sends a
message to the referee, and the referee is asked to estimate $g_{i}$ based on
an index $i\in[t]$ together with the auxiliary information of
$f_{i+1},\dots,f_{t}$. Here for convenience we let $f_{i}\in[\pm n]$ denote
the bias of the number of underlying $\textsc{Sum-Equal}_{k}$ instances
outputting $1$ in $g_{i}$, and the corresponding Hamming norm is actually
$f^{\prime}_{i}:=(n+f_{i})/2$. More specifically, $g_{i}=1$ if
$f_{i}\geq\varepsilon{n}$ and $g_{i}=-1$ if $f_{i}\leq-\varepsilon{n}$, and
$g_{i}$ is undefined otherwise.

For the reduction, we let the $i$-th $\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$
instance $g_{i}$ in the $\textsc{Aug-Index-GHSE}_{n,k}^{t}$ problem have
frequency $100^{i-1}$, i.e., each element in $g_{i}$ is counted $100^{i-1}$
times (as that many distinct elements). Thus the universe contains
$N:=n+100\cdot n+\dots+100^{t-1}\cdot n\leq 100^{t}n/99$ distinct elements in
total, which is $N\leq n^{1.01}$ for sufficiently small $t$ (and hence
$1/N^{0.49}>1/\sqrt{n}$). The final Hamming norm is a weighted sum
$F^{\prime}:=\sum_{i=1}^{t}100^{i-1}f^{\prime}_{i}$. The advantage of
$F^{\prime}$ is hence $F:=2F^{\prime}-N=\sum_{i=1}^{t}100^{i-1}f_{i}$.

Then we invoke the simultaneous communication protocol for
$\textsc{T}_{\varepsilon}$ to estimate $F^{\prime}$, which returns a value
$\widetilde{F^{\prime}}$ satisfying
$(1-\varepsilon)F^{\prime}\leq\widetilde{F^{\prime}}\leq(1+\varepsilon)F^{\prime}$.
Translating to the advantage we get $\left|\widetilde{F}-F\right|\leq
2\varepsilon F^{\prime}\leq 2\varepsilon N$. From this approximated value
$\widetilde{F}$, together with the index $i$ and auxiliary information
$f_{i+1},\dots,f_{t}$, we need to determine the output value of $g_{i}$. Since
the influence of $f_{j}$ with $j>i$ can be precisely removed from $F$ before
getting the approximated norm $\widetilde{F}$, in what follows it suffices to
consider the estimation of $g_{t}$ when the index is indeed $i=t$. Recall that
$F=100^{t-1}f_{t}+\sum_{i=1}^{t-1}100^{i-1}f_{i}$, and thus $\widetilde{F}$ is
also an approximation of $100^{t-1}f_{t}$ as long as the additive error
$\sum_{i=1}^{t-1}100^{i-1}f_{i}$ is bounded.

Let the input distribution to every $f_{i}$ be padded from the
$1$-$\textsc{GHSE}_{n^{\prime}}$ distribution $\mu$ as in Lemma 7.5, and we
consider the probability over the random choices of hash functions in what
follows. Then $f_{i}$ has expectation $\pm 10\varepsilon n$ and variance
bounded by $\varepsilon^{2}n^{2}$. It immediately follows that
$\Pr\left[|f_{i}|\geq 20\varepsilon n\right]\leq 1/100$. Similarly,
$\Pr\left[|f_{i}|\geq 20^{j}\varepsilon n\right]\leq
1/(20^{j}-10)^{2}<1/100^{j}$. Therefore,

$\displaystyle\Pr\left[\left|\sum_{i=1}^{t-1}100^{i-1}f_{i}\right|>100^{t-1}\varepsilon
n\right]$
$\displaystyle\leq\sum_{i=1}^{t-1}\Pr\left[\left|f_{t-i}\right|>20^{i}\varepsilon
n\right]<\sum_{i=1}^{t-1}\frac{1}{100^{i}}\leq\frac{1}{99}$ (9)

where the first inequality holds because if $\left|f_{t-i}\right|\leq
20^{i}\varepsilon n$ for every $i$, then
$\left|\sum_{i=1}^{t-1}100^{i-1}f_{i}\right|\leq\sum_{i=1}^{t-1}100^{i-1}\times
20^{t-i}\varepsilon n\leq\frac{20^{t}}{100}\varepsilon
n\sum_{i=1}^{t-1}5^{i}<100^{t-1}\varepsilon n$.

On the other hand, we notice that $\Pr\left[f_{t}\leq 5\varepsilon
n\;|\;g_{t}=1\right]\leq 1/25$. Thus

$\displaystyle\Pr\left[F\leq 4\times 100^{t-1}\varepsilon
n\;|\;g_{t}=1\right]$ $\displaystyle\leq
1-\Pr\left[\left(f_{t}>5\cdot\varepsilon
n\right)\land\left(\left|\sum_{i=1}^{t-1}100^{i-1}f_{i}\right|\leq
100^{t-1}\varepsilon n\right)\;\Big{|}\;g_{t}=1\right]$
$\displaystyle\leq\Pr\left[f_{t}\leq 4\varepsilon
n\;|\;g_{t}=1\right]+\Pr\left[\left|\sum_{i=1}^{t-1}100^{i-1}f_{i}\right|>100^{t-1}\varepsilon
n\right]\leq\frac{1}{25}+\frac{1}{99}<\frac{1}{10}$ (10)

And symmetrically we have

$\displaystyle\Pr\left[F\geq-4\times 100^{t-1}\varepsilon
n\;|\;g_{t}=0\right]<\frac{1}{10}$ (11)

Recalling that $N\leq 100^{t}n/99$, we have $4\times 100^{t-1}\varepsilon
n\geq\frac{4\times 99}{100}\cdot\varepsilon N>3\varepsilon N$. Notice that as
long as $\widetilde{F}$ is a $(1\pm\varepsilon)$-approximation of $F$, there
is $\left|\widetilde{F}-F\right|\leq 2\varepsilon N$. Suppose
$\textsc{T}_{\varepsilon}$ succeeds with probability $2/3$,

$\Pr\left[\widetilde{F}>\varepsilon
N\;|\;g_{t}=1\right]\geq\Pr\left[\text{$\textsc{T}_{\varepsilon}$
succeeds}\right]\cdot\Pr\left[F>3\varepsilon
N\;|\;\text{$\textsc{T}_{\varepsilon}$ succeeds}\land
g_{t}=1\right]\geq\frac{2}{3}\times\frac{9}{10}=0.6$

and similarly $\Pr\left[\widetilde{F}<-\varepsilon N\;|\;g_{t}=0\right]\geq
0.6$. Thus we can determine the value of $g_{t}$ with probability $\geq 0.6$.
That is

$\displaystyle\mathbf{RCC}^{sim}_{k,1/3}\left(\textsc{T}_{\varepsilon}\right)\geq\mathbf{RCC}^{sim}_{k,0.4}\left(\textsc{Aug-
Index-GHSE}_{n,k}^{t}\right)$

It remains to show

$\displaystyle\mathbf{RCC}^{sim}_{k,0.4}\left(\textsc{Aug-Index-
GHSE}_{n,k}^{t}\right)\geq$
$\displaystyle{\Omega\left({t\cdot\mathbf{RCC}^{sim}_{k,0.1}\left(\text{$\varepsilon\sqrt{n}$-$\textsc{GHSE}_{n}$}\right)}\right)}$
$\displaystyle=$ $\displaystyle{\Omega\left({t\cdot\varepsilon^{-2}k\log\log
k}\right)}$

The inequality follows a similar proof as Theorem 7.7 for
$\varepsilon\geq{\Omega\left({\sqrt{\frac{\log k}{k}}}\right)}$, and the
equality follows Corollary 7.8. In particular, if there are $m=k$ updates in
total and each update is of magnitude $M=k^{{{O}\left({1}\right)}}$, and
recalling that $t=\log(n)={\Omega\left({\log(N)}\right)}$ since $N\leq
100^{t}n/99$, we can conclude

$\mathbf{RCC}^{sim}_{m,1/3}\left(\textsc{T}_{\varepsilon}\right)\geq\mathbf{RCC}^{sim}_{k,0.4}\left(\textsc{Aug-
Index-
GHSE}_{n,k}^{t}\right)={\Omega\left({\varepsilon^{-2}m\log(N)\log\log(mM)}\right)}$

Combining the above with Lemma 2.1 and Theorem 4.1 of [2], we conclude that in
the strict turnstile model
$\overrightarrow{\mathbf{RSC}}_{1/3}\left(\textsc{T}_{\varepsilon}\right)={\Omega\left({\varepsilon^{-2}\log(N)\log\log(mM)}\right)}$.
Thus we complete the proof.

## References

  * [1] Farid Ablayev.  Lower bounds for one-way probabilistic communication complexity and their application to space complexity.  Theoretical Computer Science, 157(2):139–159, 1996.
  * [2] Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff.  New characterizations in turnstile streams with applications.  In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 20:1–20:22, 2016.
  * [3] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar.  An information statistics approach to data stream and communication complexity.  Journal of Computer and System Sciences, 68(4):702–732, June 2004\.
  * [4] Paul Beame, Toniann Pitassi, Nathan Segerlind, and Avi Wigderson.  A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness.  In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 52–66, 2005.
  * [5] Mark Braverman and Ankit Garg.  Public vs private coin in bounded-round information.  In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 502–513, 2014.
  * [6] Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, and Nikolay K. Vereshchagin.  Towards a reverse newman’s theorem in interactive information complexity.  Algorithmica, 76(3):749–781, 2016 (also CCC 2013).
  * [7] Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan.  Comparing data streams using hamming norms (how to zero in).  IEEE Trans. Knowl. Data Eng., 15(3):529–540, 2003.
  * [8] André Gronemeier.  Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness.  In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, pages 505–516, 2009.
  * [9] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  J. ACM, 53(3):307–323, 2006.
  * [10] T. S. Jayram.  Hellinger strikes back: A note on the multi-party information complexity of and.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX ’09 / RANDOM ’09, Berkeley, CA, USA, August 21 - 23, 2009, pages 562–573, 2009.
  * [11] Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff.  Fast moment estimation in data streams in optimal space.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 745–754, 2011\.
  * [12] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  On the exact space complexity of sketching and streaming small norms.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1161–1178, 2010.
  * [13] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  An optimal algorithm for the distinct elements problem.  In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 41–52, 2010.
  * [14] Ilan Kremer, Noam Nisan, and Dana Ron.  On randomized one-round communication complexity.  Computational Complexity, 8(1):21–49, 1999.
  * [15] Eyal Kushilevitz.  Communication complexity.  Advances in Computers, 44:331–360, 1997.
  * [16] Yi Li, Huy L. Nguyen, and David P. Woodruff.  Turnstile streaming algorithms might as well be linear sketches.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 174–183. ACM, 2014.
  * [17] Ilan Newman.  Private vs. common random bits in communication complexity.  Information processing letters, 39(2):67–71, 1991.
  * [18] Christos H. Papadimitriou and Michael Sipser.  Communication complexity.  Journal of Computer and System Sciences, 28(2):260–269, 1984.
  * [19] Emanuele Viola.  The communication complexity of addition.  SODA, 2013.
  * [20] David P. Woodruff and Qin Zhang.  Tight bounds for distributed functional monitoring.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 941–960, 2012.

##  Appendix A Communication Upper Bound for Equality

The standard $\delta$-error protocol solving the Equality problem starts by
sending and comparing the digest under a random hash function $h:[p]\to[q]$
where $q={{O}\left({\delta^{-1}\log p}\right)}$. For example, let $q$ be a
random prime drawn from the interval
$[\delta^{-2}\log^{2}p,2\delta^{-2}\log^{2}p]$ and let $h$ compute a number
modulo $q$. By the prime number theorem there are at least $2\sqrt{N}$ primes
in the interval $[N,2N]$, which implies the existence of $2\delta^{-1}\log(p)$
distinct primes in that range. For any two distinct numbers
$x,y\in\mathbb{Z}_{p}$, since $z=x-y$ has no more than $\log|z|\leq\log p$
prime factors, the error probability of the protocol is bounded by the
collision probability of $h$ as follows:

$\Pr_{q}\left[h(x)=h(y)\right]=\Pr_{q}\left[x\equiv
y\pmod{q}\right]=\Pr_{q}\left[q|(x-y)\right]\leq\frac{\log p}{2\delta^{-1}\log
p}<\delta$

The communication is a message of the form $(h,h(x))$ (indeed $(q,x\mod q)$ in
the above example), whose length is at most $2{\left\lceil{\log
q}\right\rceil}={{O}\left({\log(1/\delta)+\log\log
p}\right)}={{O}\left({\log(1/\delta)+\log\log k}\right)}$ bits. In particular
this is an upper bound for one-way communication protocols computing Equality.
Recalling that $p={\Theta\left({k^{1/4}}\right)}$, we can conclude

$\mathbf{RCC}_{2,\delta}(f)\leq\overrightarrow{\mathbf{RCC}}_{2,\delta}(f)={{O}\left({\log(1/\delta)+\log\log
k}\right)}$

We note that the $1/\delta$ factor in $q$ is unavoidable, since otherwise more
than an $\delta$ fraction of numbers would share the same message and hence
the collision probability, as well as the error probability, would exceed
$\delta$.

##  Appendix B The lower bound for Aug-Index-Sum-Equal over integers

In this part, we prove our lower bound for the $\textsc{Aug-Index-Sum-
Equal}_{k}^{m}$ problem defined as follows:

  * •

there are $m$ copies of $\textsc{Sum-Equal}_{k}^{(1)},\ldots,\textsc{Sum-
Equal}_{k}^{(m)}$ and $k$ players, among which the last player is the
_referee_ ;

  * •

each of the $k-1$ players has inputs to the $m$ copies of $\textsc{Sum-
Equal}_{k}$, and sends one message to the referee (denote these messages by
$M_{1},\ldots,M_{k-1}$);

  * •

the referee gets inputs to the $m$ copies as well, together with an index
$n\in[m]$ and the answers to $\textsc{Sum-
Equal}_{k}^{(n+1)},\ldots,\textsc{Sum-Equal}_{k}^{(m)}$;

  * •

on receiving the other $k-1$ players’ messages, the referee outputs an
estimate of $\textsc{Sum-Equal}_{k}^{(n)}$.

Theorem 7.7 (restated). Let $\Pi$ be the $\delta$-error simultaneous
$k$-player protocol for the $\textsc{Aug-Index-Sum-Equal}_{k}^{m}$ problem,
where $m\leq\frac{k\log\log k}{20\log k}$ and the error tolerance
$\delta\in(0,1/6)$. The simultaneous communication complexity of $\Pi$ is
$\mathbf{RCC}^{sim}_{k,\delta}(\Pi)={\Omega\left({mk\log\log k}\right)}$.

######  Proof B.1.

To prove the ${\Omega\left({mk\log\log k}\right)}$ lower bound we will deduce
a contradiction if $\Pi$ uses $c<\gamma mk\log\log k$ bits of communication,
for a _sufficiently small_ constant $\gamma$. By decreasing $\gamma$ we may
assume that $k$ is arbitrarily large.

For the hard distribution we first introduce a magnitude bound
$a:=\gamma^{\prime}\log k$ where $\gamma^{\prime}$ is a sufficiently small
constant. Then we let $M$ be the smallest integer such that $\forall
a^{\prime}\in\mathbb{Z},1\leq a^{\prime}\leq a$, $M$ is a multiple of
$a^{\prime}$. By the following claim from Viola’s work we know $M$ is bounded
by $k^{1/8}$ when $\gamma^{\prime}$ is sufficiently small.

######  Claim 4 (Claim 37 in [19]).

$M\leq 2^{{{O}\left({a}\right)}}$. Let $c^{\prime}$ be the constant in
${{O}\left({a}\right)}={{O}\left({\gamma^{\prime}\log k}\right)}$ and
$\gamma^{\prime}$ be sufficiently small. Then $M\leq 2^{c^{\prime}a}\leq
k^{1/8}.$

Now we specify the distribution $\mathcal{H}$ for the $\textsc{Sum-Equal}_{k}$
instances. $\mathcal{H}:=\left(G/2+B/2\right)^{m}$ consists of $m$ independent
copies of $G/2+B/2$, for $G$, $B$ defined as follows:

$\left\\{\begin{array}[]{c c
r}G:=&\big{(}G_{1},\dots,G_{k-1},&-\sum_{j=1}^{k-1}G_{j}\big{)}\\\
B:=&\big{(}B_{1},\dots,B_{k-1},&M-\sum_{j=1}^{k-1}B_{j}\big{)}\end{array}\right.$

where $G_{j},B_{j}$ are uniformly and independently chosen from $[a]$ for
every $j\in[k-1]$. Note that: a) $\textsc{Sum-Equal}_{k}(G)=0$, $\textsc{Sum-
Equal}_{k}(B)=1$; b) the first $k-1$ elements of $G$ and $B$, denoted by
$G_{-k}$ and $B_{-k}$, are the same uniform distribution over $[a]^{k-1}$.
Thus we can write $B=(G_{-k},M+G_{k})$; c) for $j\in[k-1]$, the $j$-th
player’s input $\mathcal{H}_{j}$ is uniform over $[a]^{m}$ and independent
from other players’ input.

Besides $\mathcal{H}_{k}$, the referee gets in addition an index $n$ uniformly
drawn from $[m]$ together with the answers $Y^{(j)}=\textsc{Sum-
Equal}_{k}(X^{(j)})$ for $j=n+1,\ldots,m$. Let
$\mathcal{H}_{n}^{\prime}:=(\mathcal{H},Y^{(n+1)},\ldots,Y^{(m)})$ and the
hard input distribution is defined as
$\mathcal{H}^{\prime}:=\sum_{n=1}^{m}\frac{1}{m}\cdot\mathcal{H}_{n}^{\prime}$.

Now we derandomize the protocol $\Pi$ by fixing the randomness and thus get an
$\delta$-error deterministic protocol $\Pi^{\prime}$ with respect to the above
input distribution. That is, $\Pi^{\prime}$ outputs $\textsc{Sum-
Equal}_{k}^{(n)}=\textsc{Sum-Equal}_{k}(X^{(n)})$ with probability $\geq
1-\delta$.

By averaging, for at least $m/2$ choices of the index $n\in[m]$ and the
restricted distribution $\mathcal{H}^{\prime}_{n}$, the error of
$\Pi^{\prime}$ is bounded by $2\delta$.

$\displaystyle\Pr_{(X,Y)\sim\mathcal{H}^{\prime}_{n}}\left[\Pi^{\prime}_{out}(\Pi^{\prime}(X,Y))\neq\textsc{Sum-
Equal}_{k}(X^{(n)})\right]\leq 2\delta$ (12)

Then we introduce Lemma B.2 that lower bounds
$I\left(X^{(n)}_{-k};M_{1},\ldots,M_{k-1}\right)\geq 0.1{k\log a}$ for
protocols with small error. For compactness the proof of Lemma B.2 is deferred
to the end of this section.

######  Lemma B.2.

For every $n$ such that $\Pi^{\prime}$ errs with probability $\leq 1/3$ on
input $(X,Y)\sim\mathcal{H}^{\prime}_{n}$, the mutual information between
$X^{(n)}$ and $\Pi^{\prime}(X,Y)$ must be
$I\left(X^{(n)}_{-k};M_{1},\ldots,M_{k-1}\right)\geq 0.1{k\log a}$.

Using Lemma B.2, it immediately follows that for $\delta\leq 1/6$ the protocol
$\Pi^{\prime}$ must use ${\Omega\left({mk\log a}\right)}$ bits of
communication. Since

$\displaystyle\mathbf{RCC}^{sim}_{k,\delta}(\Pi^{\prime})$ $\displaystyle\geq
I\left(X_{-k};M_{1},\dots,M_{k-1}\right)$
$\displaystyle=\sum_{i=1}^{m}I\left(X^{(i)}_{-k};M_{1},\dots,M_{k-1}\;|\;X^{(1)}_{-k},\ldots,X^{(i-1)}_{-k}\right)$
$\displaystyle=\sum_{i=1}^{m}I\left(X^{(i)}_{-k};M_{1},\dots,M_{k-1},X^{(1)}_{-k},\ldots,X^{(i-1)}_{-k}\right)$
$\displaystyle\geq\sum_{i=1}^{m}I\left(X^{(i)}_{-k};M_{1},\dots,M_{k-1}\right)$
$\displaystyle\geq\frac{m}{2}\cdot 0.1k\log a={\Omega\left({mk\log a}\right)}$

######  Proof B.3 (Proof of Lemma B.2).

Suppose by contradiction that
$I\left(X^{(n)}_{-k};M_{1},\ldots,M_{k-1}\right)<0.1k\log a$ and recall that
$m\leq\frac{k\log\log k}{20\log k}\leq\frac{0.1k\log a}{\log(ka)}$ for
$a=\gamma^{\prime}\log k$ and sufficiently large $k$,

$I\left(X^{(n)}_{-k};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right)<0.1k\log
a+{m\log(ka)}<0.2k\log a$

Therefore, recalling that $I(A;B,C)=I(A;B\;|\;C)$ when $A$ is independent from
$C$ and that $X_{j}^{(n)}$ is independent from
$X^{(n)}_{1},\ldots,X^{(n)}_{j-1}$,

$\displaystyle\sum_{j=1}^{k-1}I\left(X^{(n)}_{j};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{k-1}I\left(X^{(n)}_{j};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)},X^{(n)}_{1},\ldots,X^{(n)}_{j-1}\right)$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{k-1}I\left(X^{(n)}_{j};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\;|\;X^{(n)}_{1},\ldots,X^{(n)}_{j-1}\right)$
$\displaystyle\leq$ $\displaystyle
I(X^{(n)}_{-k};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)})<0.2k\log
a$

As a result, there is $J\subseteq[k-1]$ and $|J|>k/2$ such that for every
$j\in[k-1]$, it holds that
$I\left(X^{(n)}_{j};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right)<-1+0.5\log
a$, and hence

$\displaystyle\mathsf{H}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]$
$\displaystyle=$
$\displaystyle\mathsf{H}\left[X^{(n)}_{j}\right]-I\left(X^{(n)}_{j};M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right)$
$\displaystyle>$ $\displaystyle\log a-(-1+0.5\log a)=1+0.5\log a$ (13)

Note that
$\mathsf{H}_{\infty}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]<1$
implies the existence of $x\in[a]$ such that
$\Pr\left[X^{(n)}_{j}=x\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]=p_{x}>\frac{1}{2}$,
and hence it follows that

$\displaystyle\mathsf{H}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]=$
$\displaystyle\sum_{i\in[a]}p_{i}\log\frac{1}{p_{i}}$ $\displaystyle\leq$
$\displaystyle p_{x}\log\frac{1}{p_{x}}+(1-p_{x})\log\frac{a-1}{1-p_{x}}$
$\displaystyle<$ $\displaystyle 1+0.5\log(a-1)$ (14)

Thus, (13) ensures that
$\mathsf{H}_{\infty}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]\geq
1$ for every $j\in J$. In what follows, we prove that if
$\mathsf{H}_{\infty}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]\geq
1$ for every $j\in J$ and $|J|>k/2$, then the conditional distribution
$B_{k}^{\prime}:=G_{k}^{\prime}+M$ and
$G_{k}^{\prime}:=-\sum_{j=1}^{k-1}X^{(n)}_{j}\;\Big{|}\;{\left\\{{M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}}\right\\}}$
have statistical distance $\leq k^{-1/8}$.

Notice that for $j\in J$ and
$\mathsf{H}_{\infty}\left[X^{(n)}_{j}\;|\;M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}\right]\geq
1$, the conditional distribution
$G^{\prime}_{j}:=X^{(n)}_{j}\;\Big{|}\;{\left\\{{M_{1},\ldots,M_{k-1},X_{k},Y^{(n+1)},\ldots,Y^{(m)}}\right\\}}$
is a convex combination of distributions uniform over two values. More
specifically, $G^{\prime}_{j}=\sum_{v_{j}}\alpha_{v_{j}}\cdot G^{[v_{j}]}$,
where $\alpha_{v_{j}}\in(0,1)$ and each $G^{[v_{j}]}$ is a random variable
uniform over two values. For $j\notin J$,
$G^{\prime}_{j}=\sum_{v_{j}}\alpha_{v_{j}}\cdot G^{[v_{j}]}$ where
$G^{[v_{j}]}$ is fixed, i.e., a random variable that equals one value with
probability $1$. For $v=(v_{1},\dots,v_{k-1})$, let
$\alpha_{v}=\prod_{j=1}^{k-1}\alpha_{v_{j}}$ and
$G^{[v]}=\left(G^{[v_{1}]},\ldots,G^{[v_{k-1}]},-\sum_{j=1}^{k-1}G^{[v_{j}]}\right)$,
then $G^{\prime}$ can be decomposed as $G^{\prime}=\sum_{v}\alpha_{v}\cdot
G^{[v]}$.

Now for every $j\in J$ and $G^{[v_{j}]}$ uniform over
${\left\\{{a_{j},b_{j}}\right\\}}\subset[a]$, we can assume w.l.o.g.,
$a_{j}<b_{j}$ and write $G^{[v_{j}]}=a_{j}+(b_{j}-a_{j})Z_{j}$ where $Z_{j}$
is uniform over $\\{0,1\\}$. Since $b_{j}-a_{j}\in[a]$, among the $>k/2$
indices $j\in J$ for which $G^{[v_{j}]}$ takes two values, we must have
$t\geq|J|/a>k/{{O}\left({\log k}\right)}>\sqrt{k}$ indices $J^{\prime}$ such
that for any $j\in J^{\prime}$ the value $b_{j}-a_{j}$ is the same value
$M^{\prime}$.

Thus $G^{[v]}$ can be further decomposed into a convex combination of
$G^{\left\\{{u}\right\\}}$ where, among the indices in $J$, only those in
$J^{\prime}$ are not fixed. Fix any $u$ and denote $G^{\left\\{{u}\right\\}}$
by $G^{\prime\prime}$. Let $S=\sum_{j\in J^{\prime}}Z_{j}$ denote the sum of
$t$ uniform i.i.d. $0/1$ random variables. Then we can write

$\displaystyle G^{\prime\prime}_{k}$ $\displaystyle=b+M^{\prime}S$
$\displaystyle B^{\prime\prime}_{k}$ $\displaystyle=b+M^{\prime}S+M$

Since $1\leq M^{\prime}<a$, $M^{\prime}$ divides $M$ and hence $M=M^{\prime}q$
for $q\in\mathbb{Z}$ and $q\leq M\leq k^{1/8}$. Now we can apply $q$ times the
shift-invariance of the binomial distribution, which is stated as follows:

######  Claim 5 (Claim 39 in [19]).

Let $S$ be the sum of $t$ uniform, i.i.d. Boolean random variables. Then $S$
and $S+1$ have statistical distance $\leq{{O}\left({1/\sqrt{\ell}}\right)}$.

This yields that $G^{\prime\prime}_{k}$ and $B^{\prime\prime}_{k}$ have
statistical distance

$SD(G^{\prime\prime}_{k},B^{\prime\prime}_{k})=SD(M^{\prime}\cdot
S,M^{\prime}\cdot(q+S))\leq q\cdot{{O}\left({1/\sqrt{\sqrt{k}}}\right)}\leq
k^{1/8}/k^{1/4}=k^{-1/8}$

Recalling that $G^{\prime}$ is just a convex combination of
$G^{\prime\prime}$, the statistical distance between $G^{\prime}_{k}$ and
$B^{\prime}_{k}=G^{\prime}_{k}+M$ is also bounded by $k^{-1/8}$. However, by
definition of $G^{\prime}_{k}$ and $B^{\prime}_{k}$ we conclude that the
referee cannot distinguish the two cases of $X^{(n)}\sim G$ and $X^{(n)}\sim
B$ with advantage greater than $k^{-1/8}<1/6$, which contradicts the condition
that $\Pi^{\prime}$ has error probability $<1/3$.

Therefore, $I\left(X^{(n)}_{-k};M_{1},\ldots,M_{k-1}\right)\geq 0.1k\log
a={\Omega\left({k\log a}\right)}$.