There exists a distribution \(\mu _H\) , which is product on any
\(k-1\)  out of \(k\)  players, for which
\(\mathbf {RCC}_{k,\error }^{\mu }(f)= {\Omega \left( {k\log k} \right)}\) 
as long as \(\error \le 1/3\) .
For \(\error \ge 1/\mathsf {poly}(t)\) ,
the gap between \(\mathbf {RCC}_{k,\error }^{\mu }(f)\)  and \(\overrightarrow{\mathbf {RCC}}_{t,\error }^{\mu }(f)\)  is bounded as below:
\(\mathbf {RCC}_{k,\error }^{\mu }(f) \;\big /\; \overrightarrow{\mathbf {RCC}}_{t,\error }^{\mu }(f) = {\Omega \left( {\frac{k\log k}{t\log t}} \right)}\) 
The outline of the proof of theorem:log-separation was given in Section .
That is, the upper bound in part (a) follows from applying \(k = t\)  in
the first part of Lemma REF ,
while the lower bound in part (b) follows from the second part of Lemma REF .
Tightness of the Communication Complexity Separation
The following theorem and corollary show tightness of our separations.

For every \(k\) -party function \(f: \Sigma ^k\rightarrow \Gamma \) , product distribution \(\mu \)  over \(\Sigma ^k\) , and error tolerance \(\error <1/3\) ,
if the optimal \(\error \) -error 2-player one-way protcol for \(f\)  does not degenerate to the deterministic case,
then the following holds:
\({\overrightarrow{\mathbf {RCC}}_{k,\error }^{\mu }(f)}\; \big /\; {\overrightarrow{\mathbf {RCC}}_{2,\error }(f)} \le &{{O} \left( {k \cdot \left(1+\frac{\log k}{\log (1/\error )}\right) } \right)}= {\left\lbrace \begin{array}{ll}{{O} \left( {k\log k} \right)} & \mbox{if $\error ={{\Omega \left( {1} \right)}}$}\\{{O} \left( {k} \right)} & \mbox{if $\error =1/k^{{\Omega \left( {1} \right)}}$}\end{array}\right.}\) 

In particular,
\(\overrightarrow{\mathbf {RCC}}_{k,\error }^{\mu }(f) =& {\left\lbrace \begin{array}{ll}{{O} \left( {k\log k} \right)} \cdot \overrightarrow{\mathbf {RCC}}_{2,\error }(f) & \mbox{if $\error ={{\Omega \left( {1} \right)}}$}\\{{O} \left( {k} \right)} \cdot \overrightarrow{\mathbf {RCC}}_{2,\error }(f)+{{O} \left( {k\log k} \right)} & \mbox{if $\error \le 1/k^{{\Omega \left( {1} \right)}} $}\end{array}\right.}\) 
First we let \(\Pi _0\)  be the optimal \(\error \) -error 2-player one-way protocol \(\Pi _0\)  that computes \(f\)  with communication \(C=\overrightarrow{\mathbf {RCC}}_{2,\error }(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 = \error ^2/(16k^2)\)  and communication \({C M}\) .
Recall that \(\Pi _0\)  has \(\error <1/3\) , it suffices to let \(t\)  and \(M\)  in Lemma REF  be as follows:
\(t &=  {\left\lceil {\log \left(\error /(16k^2) \right)/\log \left(4\error (1-\error ) \right)} \right\rceil }\\M &=1+2t=1+2 {\left\lceil {\frac{\log (1/\error )+2\log k+4}{\log (1/\error )+\log (1/(1-\error ))-2}} \right\rceil }={\Theta \left({1+\frac{\log k}{\log (1/\error )}} \right)} \) 
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]=\error <1/2\)  for every \(i\in [t]\) ,
and let \(Y=\mathbf {Majority}{\left\lbrace {X_1,\dots , X_{2t+1}} \right\rbrace }\)  be the majority of all \(X_i\) 's.
Then \(\Pr [Y=1]\le \varepsilon \)  as long as \(t\ge \log (\varepsilon /\error )/\log (4\error (1-\error ))\) .
For \(0<\error <1/2\)  and \(t\ge \log (\varepsilon /\error )/\log (4\error (1-\error ))\) ,
we have
\(\Pr \left[ Y=1 \right] &= \Pr \left[ |{\left\lbrace {iX_i=1} \right\rbrace }|\ge t+1 \right]\\&= \sum _{j=t+1}^{2t+1} \binom{2t+1}{j} \error ^j(1-\error )^{2t+1-j}\\&\le \sum _{j=t+1}^{2t+1} \binom{2t+1}{j} \error ^{t+1}(1-\error )^{t}\\&=\frac{2^{2t+1}}{2} \cdot \error ^{t+1}(1-\error )^{t}=\left( 4\error (1-\error ) \right)^t \cdot \error \\&\le \frac{\varepsilon }{\error } \cdot \error =\varepsilon \) 
The first inequality holds because \(\error <1/2\)  and hence \(\error ^j(1-\error )^{2t+1-j}\le \error ^{t+1}(1-\error )^{t}\)  for \(j\ge t+1\) . The second inequality holds because \(4\error (1-\error )<1\)  for \(\error <1/2\) , and \(\left( 4\error (1-\error ) \right)^t\le \left( 4\error (1-\error ) \right)^{\log (\varepsilon /\error )/\log (4\error (1-\error ))} = \varepsilon /\error \) .
Thus, we have proved that \(\Pr [Y=1]\le \varepsilon \)  for \(t \ge {\log (\varepsilon /\error )/\log (4\error (1-\error ))}\) .
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 \(\error >0\) , since the error probability must be \(\error \ge 1/2^C\)  if it is not zero, and hence \(M={\Theta \left({1+\frac{\log k}{\log (1/\error )}} \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 \(\error /2\)  with respect to \(\mu \) .
The idea is that given the product input distribution \(\mu \) , each player \(P_i\)  acts as follows:

\(P_i\)  first assumes that the received message \(m_{i-1}\)  from \(P_{i-1}\)  will lead to a correct answer with probability \(\ge 1-\frac{\error }{4k}\)  with respect to \(\mu \) .

\(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 \(\ge 1-\frac{\error }{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).

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{\error }{4k}+\frac{\error }{4k})<\error /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,\error }^{\mu }(f)\le {{O} \left( {kCM} \right)}\) .
Notice that in the proof of Theorem REF , 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.
For every \(k\) -party function \(f\)  and product input distribution \(\mu \) , and for every \(\error < 1/3\) ,
\(\mathbf {RSC}_{\error }^{\mu }(f) \le \overrightarrow{\mathbf {RSC}}_{\error }^{\mu }(f) \le {{O} \left( {1+\frac{\log k}{\log (1/\error )}} \right)} \cdot \overrightarrow{\mathbf {RCC}}_{2,\error }(f).\)

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 \(\error < 1/9\) , but lower bounds for large error tolerance such as \(\error =1/3\)  can be obtained using a standard error amplification argument.
Let \(F:\left(\mathbb {Z}_p^m\right)^k \rightarrow  \lbrace  0, 1 \rbrace  ^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 \(\error \in (0,1/9)\) ,
we say a protocol \(\Pi \)  is correct with probability \(1-\error \)
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-\error \) , over the internal randomness of \(\Pi \) .
Then the communication cost of any \(\Pi \)  which is correct with probability \(1-\error \) , is \({\Omega \left( {m k\log k} \right)}\) .
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 \(\error \) -error randomized protocol for \(F\) , and let \(\Pi _{out}\left(x\right)\)  denote the output of \(\Pi \)  on input \(x\) .
Here by “the \(\error \) -error protocol” we mean that the expected error rate of \(\Pi \)  is bounded by \(\error \) , since both \(\Pi _{out}(x)\)  and \(F(x)\)  are binary vectors in \( \lbrace  0, 1 \rbrace  ^m\) .
Therefore,
\(\Pr _{i\in _R [m]}\left[\Pi _{out}\left(x\right)_i \ne F_i(x) \right]\le \error \) 
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,
\(\mathbf {E}\left[ \left|\Pi _{out}\left(x\right) - F(x)\right| \right]\le \error m\) 
To prove that \(\mathbf {RCC}_{k,\error }(F) = \max _{x}|\Pi (x)|={\Omega \left( {m k\log k} \right)}\)  for the optimal \(\error \) -error protocol \(\Pi \) ,
we will deduce a contradiction if \(\Pi \)  uses \(c<\gamma m k\log k\)  bits of communication,
for a constant \(\gamma =(1-9\error )/135>0\)  and sufficiently large \(k\) .
Thus, we can conclude a communication lower bound of \(c\ge \gamma mk\log k= {\Omega \left( {m k \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 \(\error \)  for inputs drawn from \(\mathcal {H}\) .
\(\mathbf {E}_{X\sim \mathcal {H}}\left[ \left| \Pi ^{\prime }_{out}(X) - F(X)\right| \right]\le \error 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)| \le \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\) ,
\(\Pr _{X\sim \mathcal {H}}\left[ \left| \Pi ^{\prime }_{out}(X) - F(X)\right| > \varepsilon m \right] \le \frac{\mathbf {E}_{X\sim \mathcal {H}}\left[ \left| \Pi ^{\prime }_{out}(X) - F(X)\right| \right]}{\varepsilon m}\le \frac{\error }{\varepsilon }\) 
Now we specify the distribution \(\mathcal {H}\) .
Let \(G\) , \(B\)  be defined as
\(\left\lbrace \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  \lbrace  0, 1 \rbrace  ^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 \( \lbrace  0, 1 \rbrace  ^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 \(\le \error \)  w.r.t. \(\mathcal {H}\) ,
we recall the following protocol decomposition by monochromatic rectangles, c.f. Claim 24 in [1]} or Lemma 1.16 in [2]}.
[[1]}, Claim 24]
A \(k\) -player (number-in-hand) deterministic protocol using communication \(\le c\)  partitions the inputs into \(C\le 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\le 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.
For every rectangle \(R\)  satisfying \(\Pr [\mathcal {H}_{-k}\in R_{-k}]\ge \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|}\) .
lem: partial uniform implies the following claim:
For every rectangle \(R\)  on which \(\Pi ^{\prime }\)  outputs \(w\in  \lbrace  0, 1 \rbrace  ^m\) ,
if \(\Pr \left[\mathcal {H}_{-k}\in R_{-k}\right]\ge \frac{1}{\alpha C}\) ,
then for every \(u\in R_k\)  and for \(\gamma ,\varepsilon \)  satisfying \(1-135\gamma \ge 3\varepsilon \) ,
\(\Pr \Big [ \mathcal {H}\in R,\; \left|F(\mathcal {H})-w\right|\le \varepsilon m \Big ]< \frac{1}{2} \Pr \left[ \mathcal {H}\in R\right]\) 
For compactness of the proof of Theorem  we defer the proofs of Claim  and Lemma  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}]\ge \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]\le \Pr [\mathcal {H}_{-k}\in R_{-k}]< \frac{1}{\alpha C} \le \frac{1}{\alpha \big |\widetilde{\mathcal {R}}\backslash \mathcal {R}\big |} \) 
Using Claim , we have
\(&\Pr _{X\sim \mathcal {H}}\left[ \left| \Pi ^{\prime }_{out}(X) - F(X)\right| \le \varepsilon m \right] \\= & \sum _{R\in \widetilde{\mathcal {R}}} \Pr \left[ \mathcal {H}\in R,\; \left|F(\mathcal {H})-\Pi ^{\prime }_{out}(R)\right|\le \varepsilon m \right] \\\le & \sum _{R\in {\mathcal {R}}} \Pr \left[ \mathcal {H}\in R,\; \left|F(\mathcal {H})-\Pi ^{\prime }_{out}(R)\right|\le \varepsilon m \right]+ \sum _{R\in \widetilde{\mathcal {R}}\backslash \mathcal {R}} \Pr [\mathcal {H}\in R] \\\le & \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] \\\le & \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 |}\le \frac{1}{2}+\frac{1}{2\alpha }\) 
Combining it with (REF ), we have
\(1-\frac{\error }{\varepsilon } \le \Pr _{X\sim \mathcal {H}}\left[ \left| \Pi ^{\prime }_{out}(X) - F(X)\right| \le \varepsilon m \right] \le \frac{1}{2}+\frac{1}{2\alpha }\Rightarrow 1-\frac{2\error }{\varepsilon }\le \frac{1}{\alpha }\) 
However, the above inequality cannot be true if we set \(\varepsilon =3\error \)  and pick a constant \(\alpha >3\) .
Let \(\gamma :=(1-9\error )/135\)  be the constant for which we want to show \(c\ge \gamma mk\log k= {\Omega \left( {m k \log k} \right)}\) .
Then \(1-135\gamma = 9\error \ge 3\varepsilon \)  satisfies the condition in claim:ball and \(\alpha ={{O} \left( {1} \right)}\)  satisfies the requirement in lem: partial uniform.
Thus we finish the contradiction argument and complete the proof of thm:A1 with \(\mathbf {RCC}_{k,\error }(F)\ge \gamma mk\log k ={\Omega \left( {m k\log k} \right)}\) .
[Proof of Claim ]
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 .
Therefore for every fixed \(u\in \mathbb {Z}_p^{|L|}\) ,
\(& \sum _{v\in  \lbrace  0, 1 \rbrace  ^{|L|}: |v|\le \varepsilon m} \Pr \left[ G^{\prime }=u-v \right]\\=& \frac{1}{2}\left(\sum _{v:|v|\le \varepsilon m}\Pr \left[G^{\prime }=u-v\right]+\sum _{v:|v|\ge |L|-\varepsilon m}\Pr \left[G^{\prime }=u-\overline{v} \right]\right)\\\le & \frac{1}{2}\left(\sum _{v:|v|\le \varepsilon m}\Pr \left[G^{\prime }=u-v\right]+\sum _{v:|v|\ge |L|-\varepsilon m}\Pr \left[G^{\prime }={u-v} \right]+\frac{2|L|}{p}\right)\\< & \frac{1}{2}\sum _{v\in  \lbrace  0, 1 \rbrace  ^{|L|}}\Pr \left[G^{\prime }={u-v} \right]\) 

where the first inequality follows Lemma ,
and the last inequality holds since as long as \(G^{\prime }\)  is close to the uniform distribution and \(|L|=(1-135\gamma )m\ge 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
\(& \sum _{v\in  \lbrace  0, 1 \rbrace  ^m: \left|v-w\right| \le \varepsilon m }\Pr \left[ G^m_k = u-v \;\Big |\;G^m_{-k}\in R_{-k} \right] \\\le & \sum _{v\in  \lbrace  0, 1 \rbrace  ^m: \left|v_L-w_L\right| \le \varepsilon m }\Pr \left[ G^m_k = u-v \;\Big |\;G^m_{-k}\in R_{-k} \right] \\= & \sum _{v_L\in  \lbrace  0, 1 \rbrace  ^{|L|}: \left|v_L-w_L\right| \le \varepsilon m }\Pr \left[ G^{(L)}_k = u_L-v_L \;\Big |\;G^m_{-k}\in R_{-k} \right] \\& \qquad \cdot \sum _{v_{-L}\in  \lbrace  0, 1 \rbrace  ^{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] \\< & \frac{1}{2} \sum _{v_L\in  \lbrace  0, 1 \rbrace  ^{|L|} }\Pr \left[ G^{(L)}_k = u_L-v_L \;\Big |\;G^m_{-k}\in R_{-k} \right] \\& \qquad \cdot \sum _{v_{-L}\in  \lbrace  0, 1 \rbrace  ^{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] \\= &\frac{1}{2} \sum _{v\in  \lbrace  0, 1 \rbrace  ^{m} }\Pr \left[ G^{m}_k = u-v \;\Big |\;G^m_{-k}\in R_{-k} \right] \) 

The above inequality (REF ) implies (REF ) since:
\(& \Pr \left[ \mathcal {H}\in R, \left|F(\mathcal {H})-w\right|\le \varepsilon m \right] \\=& \Pr \left[ \mathcal {H}_{-k}\in R_{-k} \right]\cdot \Pr \left[ \mathcal {H}_k\in R_k, \left|F(\mathcal {H})-w\right|\le \varepsilon m \;\Big |\;\mathcal {H}_{-k}\in R_{-k} \right]\\=& \Pr \left[ G^m_{-k}\in R_{-k} \right]\cdot \sum _{v\in  \lbrace  0, 1 \rbrace  ^m}\frac{1}{2^m}\Pr \left[ \mathcal {H}_k\in R_k, \left|F(\mathcal {H})-w\right|\le \varepsilon m \;\Big |\;G^m_{-k}\in R_{-k},F(\mathcal {H})=v \right]\\=& \Pr \left[ G^m_{-k}\in R_{-k} \right]\cdot \sum _{v\in  \lbrace  0, 1 \rbrace  ^m}\frac{1}{2^m}\Pr \left[ v+ G^m_k\in R_k, \left|v-w\right|\le \varepsilon m \;\Big |\;G^m_{-k}\in R_{-k} \right]\\=& \Pr \left[ G^m_{-k}\in R_{-k} \right]\cdot \sum _{v\in  \lbrace  0, 1 \rbrace  ^m: \left|v-w\right|\le \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]\\=& \frac{1}{2^m} \Pr \left[ G^m_{-k}\in R_{-k} \right]\cdot \sum _{u\in R_k} \sum _{v\in  \lbrace  0, 1 \rbrace  ^m: \left|v-w\right|\le \varepsilon m }\Pr \left[ v+ G^m_k = u \;\Big |\;G^m_{-k}\in R_{-k} \right]\\<& \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  \lbrace  0, 1 \rbrace  ^m}\Pr \left[ v+ G^m_k = u \;\Big |\;G^m_{-k}\in R_{-k} \right]\\=&\frac{1}{2} \Pr \left[ \mathcal {H}\in R\right]\) 
Thus we complete the proof of Claim 
[Proof of Lemma ]
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 \(\error _{\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 \(\error _{\ell }\) -close to uniform distribution over \(\mathbb {Z}_p^{\ell }\) .
Here the statistical error bound \(\error _{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 \(\error _{\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] \ge \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\lbrace {j\in [k-1] \; \Big | \; \Pr \left[G^m_j\in R_j\; \big | \; \mathcal {E}_x\right] \ge {1}/{\beta k^{\gamma ^{\prime } m}} } \right\rbrace }\) . Then
\(\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]\le \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|}\) 
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
\(& \Pr \left[ G^m_{-k}\in R_{-k} \;|\;\mathcal {E}_x \right] \\=&\Pr \left[G^m_{-k}\in R_{-k},\mathcal {E}_x\right] / \Pr [\mathcal {E}_x]\\= & \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] \\\ge & \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}}\) 
Combining ineq:A1upper,ineq:A1lower
and letting \(\beta \ge (\eta \alpha )^{{\gamma ^{\prime }}/{\gamma k}}\) , we can conclude
\(\left( \frac{1}{\beta k^{\gamma ^{\prime } m}} \right)^{k-1-|J_x|}\ge \frac{1}{\eta \alpha k^{\gamma mk}} \Rightarrow |J_x|\ge k-1-\frac{\gamma mk\log k+ \log \eta \alpha }{\gamma ^{\prime } m\log k + \log \beta } \ge \left(1-\frac{\gamma }{\gamma ^{\prime }}\right)k-1\) 
Thus the size of \(J_x\)  is at least
\(|J_x|\ge \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] \ge {1}/{\beta k^{\gamma ^{\prime } m}}\)  by definition of \(J_x\) 
and hence
\(\mathsf {H}\left[ G^m_j \;|\;G^m_j\in R_j,\mathcal {E}_x \right] \ge \log \left( {p^{m-\ell }}/{\beta k^{\gamma ^{\prime } m}} \right)=(m-\ell )\log p - \gamma ^{\prime } m\log k - \log \beta \) 
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)} \) :
\(\mathsf {H}[G_j^{(i)}\;|\;G_j^m\in R_j,\mathcal {E}_x ]\le 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\lbrace {i\in [m] \mathsf {H}_{\infty }\left[ G_j^{(i)}\;|\;G_j^m\in R_j,\mathcal {E}_x \right]\ge 1 } \right\rbrace } = {\left\lbrace {i \forall a, \Pr \left[ G_j^{(i)}=a\;|\;G_j^m\in R_j,\mathcal {E}_x \right]\le \frac{1}{2} } \right\rbrace }\) 
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\) .
\(\mathsf {H}\left[ G^m_j \;|\;G^m_j\in R_j,\mathcal {E}_x \right]\le & \sum _{i=1}^{m} \mathsf {H}[G_j^{(i)}\;|\;G_j^m\in R_j,\mathcal {E}_x ]\\= & \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 ] \\\le & |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 (REF ),
\((m-\ell )\log p - \gamma ^{\prime } m\log k - \log \beta & \le |I_{j,x}| \cdot \log p + (m-\ell +1 - |I_{j,x}|)(1+\log (p))/2\\\Rightarrow \left( \frac{\log p -1}{2} \right) |I_{j,x}| & \ge (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}| \ge 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] \ge \frac{1}{\eta p^{(\ell -1)(k-1)}}\) ,
the size of \(|J_x|\ge \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\lbrace {G_j^m\in R_j,\mathcal {E}_x} \right\rbrace }\)  identical to \(G_j^{(i)}\;\Big |\;{\left\lbrace {G_j^m\in R_j,\mathcal {E}_{x_j}} \right\rbrace }\) ,
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,
\(& \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] \ge \frac{1}{3}\right)\\\le & \sum _{i=\ell }^m 3 \Pr _{X_j} \left[ i\in \overline{I_{j,X_j}} \;\Big |\;j\in J_{X_j} \right] \\= & 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)\\= & 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)\\= & 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]\ge 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\lbrace {\ell ,\ell +1,\dots ,m} \right\rbrace }\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\lbrace {G_j^m\in R_j,\mathcal {E}_x} \right\rbrace }\)  denotes the conditional distribution of \(G_j^{(\ell )}\) .
Recalling that \(|J_x|\ge \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) \ge \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|\ge \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.
\(& \mathbf {E}_x\left[ \#{\left\lbrace {j\in [k-1]\text{$(\ell ,j)$ is good for $x$}} \right\rbrace } \right] \\=& \mathbf {E}_x\left[ \sum _{j=1}^{k-1} \mathcal {I}\left(\text{$(\ell ,j)$ is good for $x$}\right) \right] \\\ge & \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]\\\ge & \mathbf {E}_x\left[ \sum _{j\in J_x} \Pr _x[\ell \in I_{j,x}\;|\;j\in J_x] \right] \\\ge & \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
\(& \Pr _x\left[ \#{\left\lbrace {j\in [k-1]\text{$(\ell ,j)$ is good for $x$}} \right\rbrace } \le \frac{1}{3} \left(1-\frac{\gamma }{\gamma ^{\prime }} - \frac{27\gamma ^{\prime } m}{m-\ell +1}\right)k \right]\\\le &\exp \left( -{\Omega \left( {\left(1-\frac{\gamma }{\gamma ^{\prime }}- \frac{27\gamma ^{\prime } m}{m-\ell +1}\right)k} \right)} \right)\) 

Let \(\error ^{\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-\error ^{\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 \(\ge 1-\error ^{\prime }\) ,
the conditional distribution \(G^{\prime \prime }_k\)  is close to uniform by the following claim.
[Claim 31 in [1]}]
Let \(p\)  be a prime number.
Let \(X\)  be the sum of \(t\)  independent random variables each uniform over \({\left\lbrace {a_i,b_i} \right\rbrace }\subset \mathbb {Z}_p\)  for \(a_i\ne b_i\) .
Then \(X\)  modulo \(p\)  is \(\error \le 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 [1]} (\(G_k^{\prime \prime }\)  is \(\error ^{\prime \prime }\) -close to uniform if every component in the above convex decomposition of \(G_k^{\prime \prime }\)  is \(\error ^{\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
\(\error ^{\prime \prime } \le & 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)\\= & \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\lbrace {G_{-k}^m\in R_{-k}, G^{(1)},\dots ,G^{(\ell -1)}} \right\rbrace }\)  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
\(\error _{\ell } \le \error _{\ell -1}+ \frac{1}{\eta }+\error ^{\prime }+\error ^{\prime \prime }\) 
Let \(\gamma ^{\prime }=2\gamma \) , \(\eta =2p\)  and \(\beta =2\ge (\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 \le (1-135\gamma ) m\) , with error \(\error ^{\prime },\error ^{\prime \prime }\)  bounded by
\( \error ^{\prime }= \exp \left(-{\Omega \left( {{k}} \right)}\right), \error ^{\prime \prime }=\exp \left(-{\Omega \left( {\sqrt{k}} \right)}\right) \Longleftarrow 1-\frac{\gamma }{\gamma ^{\prime }}- \frac{27\gamma ^{\prime } m}{m-\ell +1}\ge 0.1 \Longleftrightarrow \ell \le (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 \(\error _{\ell }\) -close to uniform for \(\error _{\ell }\)  bounded by \(\frac{\ell }{p}\)  as follows:
\(\error _{\ell } \le \error _{\ell -1}+\frac{1}{\eta }+\error ^{\prime }+\error ^{\prime \prime }\le \frac{\ell -1}{p}+\frac{1}{2p}+ \exp \left(-{\Omega \left( {\sqrt{k}} \right)}\right)\le \frac{\ell }{p}\) 
Thus we have proved the induction hypothesis for every \(\ell \le (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  for \(|L|= (1-135\gamma ) m\)  and statistical distance \(\frac{|L|}{p}\) .

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 para:Hamming estimation.
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\Vert  {x} \right\Vert }_0 =|{\left\lbrace {ix_i\ne 0} \right\rbrace }|\)  and we want to output a number within \((1\pm \varepsilon )\Vert x\Vert _0\)  with probability \(\ge 2/3\) .
The strict turnstile model guarantees that \(x_i \ge 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 [6]}.
Furthermore, it is also guaranteed that for every \(i \in [N]\) , \(x_i \le \mathsf {poly}(n)\)  at the end of the stream.
In this setting, the algorithm of [7]} approximates \(\Vert x\Vert _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 spaceIndeed, 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\) .
For error tolerance \(\varepsilon <1/3\)  and \(\varepsilon =\max {\left\lbrace {{\Omega \left( { \sqrt{\frac{\log k}{k}}} \right)}, \frac{1}{{N}^{0.49}}} \right\rbrace }\) ,
any single-pass streaming algorithm solving \( \textsc {T} _\varepsilon \)  with probability \(\ge 2/3\)  in the strict turnstile model
must use \({\Omega \left( {\varepsilon ^{-2}\log (N)\log \log (mM)} \right)}\)  bits of space.
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\lbrace {\pm 1} \right\rbrace }\)  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}) \ge \varepsilon \sqrt{n}\) ,
and the output is 0 if \( \textsc {HSE} (\mathbf {x}) \le -\varepsilon \sqrt{n}\) .
Then we prove the following lemmas.

For every \(k\in \mathbb {Z}\) , \(0\le \error \le 1/2\) , and \(n\ge c^2/\varepsilon ^2=n^{\prime }\) , there is
\(\overrightarrow{\mathbf {RCC}}_{k,\error }\left(\text{$\varepsilon \sqrt{n}$-$\textsc {GHSE} _n$} \right) \ge \overrightarrow{\mathbf {RCC}}_{k,\error }\left(\text{$c$-$\textsc {GHSE} _{n^{\prime }}$} \right)\) 

[Proof of lemma:GHSE reduction]
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  \lbrace  0, 1 \rbrace  ^{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\lbrace {\pm 1} \right\rbrace }^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 \ge c\sqrt{n^{\prime }}\) ,
then \(\sum _{j}\mathbf {x}_j \ge \varepsilon n\) ,
and on the other hand
\(\sum _{j}\mathbf {x}^{\prime }_j \le -c\sqrt{n^{\prime }}\) 
implies \(\sum _{j}\mathbf {x}_j \le -\varepsilon n\) .
Thus, any \(k\) -player \(\error \) -error one-way protocol for \(\varepsilon \sqrt{n}\) -\(\textsc {GHSE} _n\)  immediately implies a \(k\) -player \(\error \) -error one-way protocol for \(c\) -\(\textsc {GHSE} _{n^{\prime }}\) .
The same argument holds in the simultaneous communication model.
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
\(\mathbf {E}\left[ \textsc {HSE} (\mathbf {x})\text{$1$-$\textsc {GHSE} _{n^{\prime }}$}(\mathbf {x})=1 \right] &= 10\sqrt{n^{\prime }}\\\mathbf {E}\left[ \textsc {HSE} (\mathbf {x})\text{$1$-$\textsc {GHSE} _{n^{\prime }}$}(\mathbf {x})=0 \right] &= -10\sqrt{n^{\prime }}\) 

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

[Proof of lemma:1-GHSE]
In this proof, we first introduce the \(\textsc {Aug-Index-Sum-Equal} \)  problem and prove that
\(\mathbf {RCC}^{sim}_{k,0.01} \left(\text{$1$-$\textsc {GHSE} _{n^{\prime }}$} \right)\ge \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 .
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 \(\text{$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\lbrace {h:\mathbb {Z}\rightarrow  \lbrace  0, 1 \rbrace  } \right\rbrace }\) ,
that is for \(x\ne 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\le n^{\prime }\) .
Alice takes \(\mathbf {m}\)  as her input in the \(\text{$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:

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.

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

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
\(\Pr \left[ m^{\prime }_i \ne m_i X^{(j)} = Y^{(j)}\right] = & \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\lbrace {j} \right\rbrace } } r_{ik} = s \;\big |\; r_{ij}=1\right] \\&+ \Pr \left[ r_{ij}=0 \right] \sum _{s=0}^{(n^{\prime \prime }-1)/2} \Pr \left[ \sum _{k\in [n^{\prime \prime }]\backslash {\left\lbrace {j} \right\rbrace } } r_{ik} = s \;\big |\; r_{ij}=0\right]\\= & \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 }\ge 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 }}}\ge 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)}\ne 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 | \ge 9\sqrt{n^{\prime }} \right]\le \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 \(\ge 0.95\)  when \(X^{(j)} = Y^{(j)}\) ,
and it outputs 0 with probability \(\ge 0.95\)  when \(X^{(j)} \ne Y^{(j)}\) .
Therefore by repeating the above procedure for every \(j\)  and taking into consideration the error probability of solving the \(\text{$1$-$\textsc {GHSE} _{n^{\prime }}$}\)  problem, Bob solves \(\textsc {Sum-Equal} _2^{(j)}\)  for every index \(j\)  with probability \(\ge 0.9\) .
That is,
\(\mathbf {RCC}^{sim}_{k,0.01} \left(\text{$1$-$\textsc {GHSE} _{n^{\prime }}$} \right)\ge \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 [8]}, [9]}.
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 ,
as proved in sec:over Z.

Let \(\Pi \)  be an \(\error \) -error randomized simultaneous \(k\) -player protocol that solves \(\textsc {Aug-Index-Sum-Equal} _k^m\) , where
\(m\le 0.1\log k\)  and the error tolerance \(\error \in (0,1/6)\) .
The simultaneous communication cost of \(\Pi \)  is \(\mathbf {RCC}^{sim}_{k,\error }(\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)}}\le k^{1/8}\)  is a multiple of all integers in \([a]\) .
Thus we finish the proof of lemma:1-GHSE.
Combining Lemma , Lemma , and Theorem 4.1 of [6]},
we get the following corollary for \(\varepsilon ={\Omega \left( {1/\sqrt{n}} \right)}\) :

For every \(k\in \mathbb {Z}\) , \(\error <1/3\) , constant \(\varepsilon \)  and \(n = {\Omega \left( {1/\varepsilon ^2} \right)}\) ,
there is
\(\mathbf {RCC}^{sim}_{k,\error }\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 \(\text{$\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\ge \varepsilon {n}\)  and \(g_i=-1\)  if \(f_i\le - \varepsilon {n}\) , and \(g_i\)  is undefined otherwise.
For the reduction, we let the \(i\) -th \(\text{$\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 \le 100^t n/99\)  distinct elements in total, which is \(N\le 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 } \le \widetilde{F^{\prime }} \le (1+\varepsilon )F^{\prime }\) .
Translating to the advantage we get \(\left| \widetilde{F} - F \right| \le 2\varepsilon F^{\prime } \le 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 ,
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 ^2n^2\) .
It immediately follows that \(\Pr \left[|f_i|\ge 20 \varepsilon n\right] \le 1/100\) .
Similarly, \(\Pr \left[|f_{i}|\ge 20^j \varepsilon n\right] \le 1/(20^j-10)^2 < 1/100^j\) .
Therefore,
\(\Pr \left[ \left|\sum _{i=1}^{t-1} 100^{i-1} f_i \right|>100^{t-1}\varepsilon n\right]& \le \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} \le \frac{1}{99}\) 

where the first inequality holds because if \(\left|f_{t-i}\right| \le 20^i \varepsilon n \)  for every \(i\) , then \( \left|\sum _{i=1}^{t-1} 100^{i-1} f_i \right|\le \sum _{i=1}^{t-1} 100^{i-1}\times 20^{t-i} \varepsilon n\le \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 \le 5\varepsilon n g_t=1\right]\le 1/25\) .
Thus
\(& \Pr \left[ F\le 4\times 100^{t-1}\varepsilon n g_t=1 \right] \\& \le 1- \Pr \left[ \left( f_t > 5\cdot \varepsilon n \right)\wedge \left( \left|\sum _{i=1}^{t-1} 100^{i-1} f_i \right|\le 100^{t-1}\varepsilon n \right) \;\Big |\; g_t=1 \right] \\&\le \Pr \left[ f_t \le 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]\le \frac{1}{25}+\frac{1}{99} <\frac{1}{10}\) 

And symmetrically we have
\(& \Pr \left[ F\ge -4\times 100^{t-1}\varepsilon n g_t=0 \right] < \frac{1}{10}\) 
Recalling that \(N\le 100^t n/99\) ,
we have \(4\times 100^{t-1}\varepsilon n \ge \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| \le 2\varepsilon N\) .
Suppose \( \textsc {T} _\varepsilon \)  succeeds with probability \(2/3\) ,
\(\Pr \left[ \widetilde{F} > \varepsilon N g_t = 1 \right]\ge \Pr \left[\text{$ \textsc {T} _\varepsilon $ succeeds}\right]\cdot \Pr \left[ F>3\varepsilon N \text{$ \textsc {T} _\varepsilon $ succeeds} \wedge g_t=1\right] \ge \frac{2}{3} \times \frac{9}{10} = 0.6\) 
and similarly \(\Pr \left[ \widetilde{F} <- \varepsilon N g_t = 0 \right]\ge 0.6\) .
Thus we can determine the value of \(g_t\)  with probability \(\ge 0.6\) .
That is
\(\mathbf {RCC}^{sim}_{k,1/3}\left( \textsc {T} _\varepsilon \right)\ge \mathbf {RCC}^{sim}_{k,0.4}\left( \textsc {Aug-Index-GHSE} _{n,k}^{t} \right)\) 
It remains to show
\(\mathbf {RCC}^{sim}_{k,0.4}\left( \textsc {Aug-Index-GHSE} _{n,k}^{t} \right)\ge & {\Omega \left( {t \cdot \mathbf {RCC}^{sim}_{k,0.1}\left(\text{$\varepsilon \sqrt{n}$-$\textsc {GHSE} _n$}\right)} \right)}\\= & {\Omega \left( {t\cdot \varepsilon ^{-2} k \log \log k} \right)}\) 
The inequality follows a similar proof as Theorem  for \(\varepsilon \ge {\Omega \left( {\sqrt{\frac{\log k}{k}}} \right)}\) , and the equality follows Corollary .
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\le 100^t n/99\) ,
we can conclude
\(\mathbf {RCC}^{sim}_{m,1/3}\left(  \textsc {T} _\varepsilon \right)\ge \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  and Theorem 4.1 of [6]},
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.

Communication Upper Bound for Equality
The standard \(\error \) -error protocol solving the \(\textsc {Equality}\)  problem starts by sending and comparing the digest under a random hash function \(h:[p]\rightarrow [q]\)  where \(q={{O} \left( {\error ^{-1}\log p} \right)}\) .
For example, let \(q\)  be a random prime drawn from the interval \([\error ^{-2}\log ^2 p, 2\error ^{-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\error ^{-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|\le \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] \le \frac{\log p}{2\error ^{-1}\log p} <\error \) 
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/\error )+\log \log p} \right)}={{O} \left( {\log (1/\error )+\log \log k} \right)}\)  bits.
In particular this is an upper bound for one-way communication protocols computing \(\textsc {Equality}\) .
Recalling that \(p={\Theta \left({k^{1/4}} \right)}\) ,
we can conclude
\(\mathbf {RCC}_{2,\error } (f) \le \overrightarrow{\mathbf {RCC}}_{2,\error }(f)={{O} \left( {\log (1/\error )+\log \log k} \right)}\) 
We note that the \(1/\error \)  factor in \(q\)  is unavoidable, since otherwise more than an \(\error \)  fraction of numbers would share the same message and hence the collision probability, as well as the error probability, would exceed \(\error \) .

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  (restated).
Let \(\Pi \)  be the \(\error \) -error simultaneous \(k\) -player protocol for the \(\textsc {Aug-Index-Sum-Equal} _k^m\)  problem, where
\(m \le \frac{k\log \log k}{20\log k}\)  and the error tolerance \(\error \in (0,1/6)\) .
The simultaneous communication complexity of \(\Pi \)  is \(\mathbf {RCC}^{sim}_{k,\error }(\Pi )={\Omega \left( {mk\log \log k} \right)}\) .


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\le a^{\prime }\le 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 37 in [1]}]
\(M\le 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\le 2^{c^{\prime }a}\le 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\lbrace \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 \(\error \) -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 \(\ge 1-\error \) .
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\error \) .
\(\Pr _{(X,Y)\sim \mathcal {H}^{\prime }_n}\left[ \Pi ^{\prime }_{out}(\Pi ^{\prime }(X,Y)) \ne \textsc {Sum-Equal} _k(X^{(n)}) \right] \le 2\error \) 
Then we introduce lemma: lb mutual information that
lower bounds \(I\left(X^{(n)}_{-k}; M_1,\ldots , M_{k-1}\right)\ge 0.1{k\log a}\)  for protocols with small error.
For compactness the proof of lemma: lb mutual information is deferred to the end of this section.
For every \(n\)  such that \(\Pi ^{\prime }\)  errs with probability \(\le 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)\ge 0.1{k\log a}\) .
Using lemma: lb mutual information, it immediately follows that for \(\error \le 1/6\)  the protocol \(\Pi ^{\prime }\)  must use \({\Omega \left( {mk\log a} \right)}\)  bits of communication.
Since
\(\mathbf {RCC}^{sim}_{k,\error }(\Pi ^{\prime }) & \ge I\left(X_{-k}; M_1,\dots ,M_{k-1} \right)\\& = \sum _{i=1}^m I\left(X^{(i)}_{-k}; M_1,\dots ,M_{k-1}\;|\;X^{(1)}_{-k},\ldots ,X^{(i-1)}_{-k} \right)\\& = \sum _{i=1}^m I\left(X^{(i)}_{-k}; M_1,\dots ,M_{k-1}, X^{(1)}_{-k},\ldots ,X^{(i-1)}_{-k} \right)\\& \ge \sum _{i=1}^m I\left(X^{(i)}_{-k}; M_1,\dots ,M_{k-1} \right)\\& \ge \frac{m}{2}\cdot 0.1 k\log a ={\Omega \left( {mk\log a} \right)}\) 
[Proof of Lemma ]
Suppose by contradiction that
\(I\left(X^{(n)}_{-k}; M_1,\ldots , M_{k-1}\right)<0.1 k\log a\)  and recall that \(m \le \frac{k\log \log k}{20\log k} \le \frac{0.1 k\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.1 k\log a + {m\log (ka)}<0.2 k\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}\) ,
\(& \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) \\\le & \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) \\= & \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)\\\le & I(X^{(n)}_{-k}; M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)} ) <0.2 k\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
\(&\mathsf {H}\left[X^{(n)}_{j} \;|\;M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)} \right] \\= &\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)\\>& \log a - (-1+ 0.5\log a) = 1+ 0.5\log a \) 
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
\(\mathsf {H}\left[X^{(n)}_{j} \;|\;M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)} \right]=& \sum _{i\in [a]} p_i\log \frac{1}{p_i} \\\le & p_x\log \frac{1}{p_x}+(1-p_x)\log \frac{a-1}{1-p_x}\\< & 1+0.5\log (a-1) \) 
Thus, (REF ) ensures that \(\mathsf {H}_{\infty }\left[X^{(n)}_{j} \;|\;M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)} \right]\ge 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]\ge 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\lbrace {M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)}} \right\rbrace }\)  have statistical distance \(\le 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]\ge 1\) ,
the conditional distribution
\(G^{\prime }_j:=X^{(n)}_{j} \;\Big |\;{\left\lbrace {M_1,\ldots , M_{k-1}, X_k, Y^{(n+1)},\ldots , Y^{(m)}} \right\rbrace }\)  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\lbrace {a_j,b_j} \right\rbrace }\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 \( \lbrace  0, 1 \rbrace  \) .
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\ge |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\lbrace {u} \right\rbrace }\)  where, among the indices in \(J\) , only those in \(J^{\prime }\)  are not fixed.
Fix any \(u\)  and denote \(G^{\left\lbrace {u} \right\rbrace }\)  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
\(G^{\prime \prime }_k &= b + M^{\prime } S\\B^{\prime \prime }_k &= b + M^{\prime } S + M\) 
Since \(1\le M^{\prime }<a\) , \(M^{\prime }\)  divides \(M\)  and hence \(M=M^{\prime }q\)  for \(q\in \mathbb {Z}\)  and \(q\le M\le k^{1/8}\) .
Now we can apply \(q\)  times the shift-invariance of the binomial distribution, which is stated as follows:
[Claim 39 in [1]}]
Let \(S\)  be the sum of \(t\)  uniform, i.i.d. Boolean random variables.
Then \(S\)  and \(S+1\)  have statistical distance \(\le {{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))\le q\cdot {{O} \left( {1/\sqrt{\sqrt{k}}} \right)}\le 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)\ge 0.1 k\log a={\Omega \left( {k\log a} \right)}\) .
