Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Green-Maimon, Naomi; Zamir, Or

doi:10.4230/LIPIcs.ICALP.2026.102

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Naomi Green-Maimon

Weizmann Institute of Science, Rehovot, Israel Or Zamir

Tel Aviv University, Israel

Abstract

Estimating the second frequency moment $F_{2}$ of a data stream up to a $(1\pm\varepsilon)$ factor is a central problem in the streaming literature. For errors $\varepsilon>\Omega(1/\sqrt{n})$ , the tight bound $\Theta\left(\log(\varepsilon^{2}n)/\varepsilon^{2}\right)$ was recently established by Braverman and Zamir. In this work, we complete the picture by resolving the remaining regime of small error, $\varepsilon<1/\sqrt{n}$ , showing that the optimal space complexity is $\Theta\left(\min\left(n,\frac{1}{\varepsilon^{2}}\right)\cdot\left(1+\left|% \log(\varepsilon^{2}n)\right|\right)\right)$ bits for all $\varepsilon\geq 1/n^{2}$ , assuming a sufficiently large universe. This closes the gap between the best known $\Omega(n)$ lower bound and the straightforward $O(n\log n)$ upper bound in that range, and shows that essentially storing the entire stream is necessary for high-precision estimation.

To derive this bound, we fully characterize the two-party communication complexity of estimating the size of a set intersection up to an arbitrary additive error $\varepsilon n$ . In particular, we prove a tight $\Omega(n\log n)$ lower bound for one-way communication protocols when $\varepsilon<n^{-1/2-\Omega(1)}$ , in contrast to classical $O(n)$ -bit protocols that use two-way communication. Motivated by this separation, we present a two-pass streaming algorithm that computes the exact histogram of a stream with high probability using only $O(n\log\log n)$ bits of space, in contrast to the $\Theta(n\log n)$ bits required in one pass even to approximate $F_{2}$ with small error. This yields the first asymptotic separation between one-pass and $O(1)$ -passes space complexity for small frequency moment estimation.

Keywords and phrases:

streaming algorithms, frequency moments, communication complexity, multipass streaming

Category:

Track A: Algorithms, Complexity and Games

Funding:

Naomi Green-Maimon: Work done while at Tel Aviv University.

Or Zamir: Supported by the Israel Science Foundation, Grant No. 1593/24, and by the Blavatnik Family foundation.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Streaming models ; Theory of computation

\rightarrow

Communication complexity

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The streaming model of computation is fundamental for processing massive datasets and has been extensively studied in both theory and practice. A central challenge in this model is the frequency moment estimation problem, in which an algorithm observes a sequence of elements from a universe $U$ and must approximate a function of their frequency distribution using limited memory. Denote by $f_{x}\in\mathbb{N}$ the number of times an element $x\in U$ appeared in the stream; the algorithm aims to return, with probability higher than $99\%$ , a $(1\pm\varepsilon)$ -estimation of $F_{p}:=\sum_{x\in U}f_{x}^{p}$ – the $p$ -th frequency moment of the stream. We generally denote the length of the stream by $n$ and assume that $|U|=\text{poly}(n)$ . In fact, we can usually assume that $|U|=O(n^{2})$ as hashing the elements into a set of size $\Theta(n^{2})$ is expected to not change the frequencies at all. The primary resource constraint studied in this setting is the amount of space required for a successful approximation. This line of research originated with the foundational work of Alon, Matias, and Szegedy [2], which both introduced this problem and established the first space-efficient algorithms for frequency moment estimation.

Among the frequency moments, the case of $p=2$ , known as second moment estimation, has particular significance. This quantity, sometimes referred to as the repeat rate or surprise index, plays a key role in applications such as database query optimization [1], network traffic anomaly detection [24], and approximate histogram maintenance [18]. For $F_{2}$ , the original algorithm proposed by Alon, Matias, and Szegedy achieves a space complexity of $O(\log n/\varepsilon^{2})$ bits. Only recently, Braverman and Zamir [8] obtained a matching lower bound for a wide range of error parameters $\varepsilon$ . They showed that for any $\varepsilon>\Omega(1/\sqrt{n})$ the optimal space complexity for estimating the second frequency moment is $\Theta(\log(\varepsilon^{2}n)/\varepsilon^{2})$ . This leaves the range of $\varepsilon<1/\sqrt{n}$ as the only range without a tight space bound for the problem. In that range, the best known lower bound is $\Omega(n)$ which follows from either [8] or the much earlier [33] for $\varepsilon=1/\sqrt{n}$ . On the other hand, by simply maintaining the entire histogram of the input stream in memory we obtain an upper bound of $O\left(n\log\left(2+\frac{|U|}{n}\right)\right)=O(n\log n)$ even for exactly computing the second frequency moment. We note that it suffices to consider only $\varepsilon\geq 1/n^{2}$ as the second frequency moment is a natural number in the range $[n,n^{2}]$ . We are thus left with a gap between the $\Omega(n)$ lower bound and $O(n\log n)$ upper bound in the range of small error $1/n^{2}\leq\varepsilon\leq 1/\sqrt{n}$ .

In this work, we establish the space complexity of second moment estimation in this remaining range of error parameters.

Theorem 1.

The space complexity of $\left(1\pm\varepsilon\right)$ -estimating the second frequency moment of a stream of $n$ elements, for any $\frac{1}{n^{2}}\leq\varepsilon\leq\frac{1}{\sqrt{n}}$ , is

\Theta\left(n\log\left(\frac{1}{\varepsilon^{2}n}\right)\right).

We observe that this bound implies a phase transition around $\varepsilon=1/\sqrt{n}$ : if the wanted error is polynomially-smaller than $1/\sqrt{n}$ then the space required is the same as needed to maintain the entire input in memory and compute an exact answer, while if $\varepsilon=1/\sqrt{n}$ then only $\Theta(n)$ bits of space are needed. Our bounds combined with those of [8] give a complete characterization of the space complexity needed to estimate the second moment up to any error parameter $\varepsilon$ . See Figure 1 for a graph. Note that both lower bounds assume that the universe of possible stream elements is sufficiently large.

Figure 1: The optimal space complexity of second moment estimation for all values of

\varepsilon

.

To derive our lower bound, we study and fully characterize the two-party communication complexity of the Approximate Set Intersection problem. In this problem, Alice and Bob are given subsets $A$ and $B$ of a larger universe $U$ , of size at most $n$ each, and need to output $|A\cap B|$ up to an additive error $\varepsilon n$ with probability at least $2/3$ . This is a natural generalization of several classical problems in communication complexity: Set Disjointness is a special case of the problem when $\varepsilon=0$ , and of Gap Hamming Distance when $\varepsilon=1/\sqrt{n}$ . When $\varepsilon<1/\sqrt{n}$ a lower bound of $\Omega(n)$ follows from [33] and a matching upper bound of $O(n)$ holds for exactly computing the intersection with two-way communication, even when the element universe $U$ is allowed to be very large [11]. To the best of our knowledge, no tight bounds were explicitly derived in all other settings and ranges of parameters. In [26] the same problem was asked and discussed, resulting only in the rather straightforward $O(\log n/\varepsilon^{2})$ upper bound obtained by Alice explicitly sending a sample of her elements to Bob. We obtain the following optimal bounds.

Theorem 2.

For $\varepsilon<1/\sqrt{n}$ , the one-way communication complexity of Approximate Set Intersection is $\Theta(n\log(2/\varepsilon^{2}n))$ and the two-way complexity is $\Theta(n)$ . For $\varepsilon\geq 1/\sqrt{n}$ the communication complexity of Approximate Set Intersection is $\Theta(1/\varepsilon^{2}+\log n)$ in both the one-way and two-way settings.

The gap between the optimal bounds for Approximate Set Intersection in the one-way and two-way communication settings implies that our lower bound for $F_{2}$ estimation in the range $\varepsilon<1/\sqrt{n}$ does not extend to multi-pass streaming algorithms. Motivated by that, we present a streaming algorithm extending the ideas from the communication protocol of Brody et al. [11], that computes an exact histogram of a stream (and in particular its exact $F_{2}$ ) using only two passes and $O(n\log\log n)=o(n\log n)$ memory.

Theorem 3.

There exists a streaming algorithm that in two passes and using $O(n\log\log n)$ bits of memory computes, with high probability, an exact histogram of the stream.

Woodruff and Zhou [35] recently showed that for $p>2$ and $\varepsilon=o(1)$ , there is an asymptotic separation between the space complexity of $F_{p}$ estimation in one-pass versus $O(1)$ -passes. Their work leaves open the question of whether such a separation also holds for “small” frequency moments (that is, $p\leq 2$ ). We show that indeed there exists such separation for $F_{2}$ , at least in the range $\varepsilon<1/\sqrt{n}$ . In the full version of this paper, we generalize this streaming algorithm for any constant number of passes $r$ and conclude that $\Theta\!\bigl(n\log^{(\Theta(r))}\!n\bigr)$ bits of memory are both necessary and sufficient for exact histogram computation, where $\log^{(k)}n$ denotes the $k$ -fold iterated logarithm.

Problem	Model	$\varepsilon<1/\sqrt{n}$	$\varepsilon\geq 1/\sqrt{n}$
Approx. Set Intersection	One-way	$\Theta(n\log(2/\varepsilon^{2}n))$	$\Theta(1/\varepsilon^{2}+\log n)$
Approx. Set Intersection	Two-way	$\Theta(n)$	$\Theta(1/\varepsilon^{2}+\log n)$
$F_{2}$ Estimation	One-pass	$\Theta(n\log(2/\varepsilon^{2}n))$	$\Theta(\log(\varepsilon^{2}n)/\varepsilon^{2})$
$F_{2}$ Estimation	Two-passes	$O(n\log\log n)$	$\begin{array}[]{l}O(\log(\varepsilon^{2}n)/\varepsilon^{2}),\Omega(1/% \varepsilon^{2}+\log n)\end{array}$

Figure 2: Complexity of Approximate Set Intersection and

F_{2}

Estimation.

See Figure 2 for a table summarizing the best-known bounds for the communication and streaming problem we discuss, with results in bold being those presented in this paper.

The space complexity of frequency moment estimation was extensively studied in many settings, and for many parameter choices [12, 33, 5, 20, 7, 27, 9, 23, 16, 17, 4, 34, 25, 3, 10, 21, 28], we refer the reader to the introduction of [8] for a more exhaustive overview of the existing literature.

2 Overview and Organization

In this section, we outline the main technical ideas behind our results and describe the organization of the rest of the paper.

Section 3: Communication lower bounds and streaming implications, in the $\varepsilon<1/\sqrt{n}$ range

We prove that any one-way communication protocol that approximates $|A\cap B|$ up to additive error $\varepsilon n$ requires $\Omega(n\log(1/\varepsilon^{2}n))$ bits when $\varepsilon<1/\sqrt{n}$ . This is shown via an information-theoretic construction inspired by the construction used by [14] to obtain a lower bound for the one-way communication complexity of Set Disjointness. We construct a large family of inputs for Alice and a small set of inputs for Bob, and show that every Alice input is uniquely identified by the answers of the communication protocol to all of Bob’s possible inputs. In a one-way communication protocol though, Alice’s message depends only on her own input and should thus intuitively encode enough information to answer any possible Bob input – which in this case results in having to fully encode her own input. Our main contribution is proving the existence of such input families, which becomes more involved in comparison to the exact problem of Set Disjointness. We then reduce from this communication problem to streaming $F_{2}$ estimation using a standard concatenation protocol, implying the same lower bound for streaming algorithms.

Section 4: Matching upper bounds via hashing

We complement the lower bounds with a simple estimator for $F_{2}$ that matches the bound up to constants. The algorithm hashes the universe into a domain of size $m=\Theta(1/\varepsilon^{2})$ using a 4-wise independent hash function, and stores the exact multiset of hash values. Here the main observation is that while the hashing induces too many collisions, we can analytically subtract the expected number of hash collisions from the observed number of collisions to obtain a significantly better estimator for the number of collisions in the original stream. We analyze the variance of the estimator and show it concentrates around the true $F_{2}$ value, yielding an estimate with additive error $\varepsilon F_{2}$ using $O(n\log(1/\varepsilon^{2}n))$ bits of memory.

Section 5: The high-error regime

We analyze the case $\varepsilon\geq 1/\sqrt{n}$ and prove that the communication complexity of approximate set intersection is $\Theta(1/\varepsilon^{2}+\log n)$ in both one-way and two-way models. Both the lower and upper bounds are essentially reductions to the $\varepsilon=\Theta(1/\sqrt{n})$ case which is very similar to the Gap Hamming Distance Problem. The lower bound is then indeed established by a reduction from the Gap Hamming Distance problem. The matching upper bound is obtained using subsampling which reduces the problem to the problem of estimating the set intersection size of two sets of some size $k$ up to an additive error of $\Theta(\sqrt{k})$ , a problem which we already present an optimal solution for in the previous sections. These simple bounds complete our characterization of the communication complexity of the Approximate Set Intersection problem.

Section 6: A two-pass algorithm for exact histograms

Motivated by the one-way/two-way gap in communication, we begin by designing a streaming algorithm that computes the exact histogram of the stream in three passes using only $O(n\log\log n)$ bits of space. The algorithm uses the first pass to hash elements into buckets and record “cheap” fingerprint-based histograms in each bucket, then uses the second pass to verify which of these histograms is correct using a randomized algebraic identity check, and finally uses the third pass to recompute the histograms of the few incorrect buckets exactly. Our algorithm builds upon the communication protocol of Brody et al. [11] for computing the exact set intersection in two-way communication, and transforms it to a streaming algorithm. One of our main technical contributions in this algorithm is constructing a streaming algorithm that can verify, in one-pass, an assumed histogram for a multiset of elements. This verification step is straightforward in the two-way communication setting, where each party can hash and compare their entire input, but requires new techniques in the streaming model. We then introduce ideas from sparse recovery to eliminate the third pass and achieve the same memory bound with a two-pass streaming algorithm. Finally, we discuss the optimality of this bound, concluding that any constant-pass algorithm for exact computation of $F_{2}$ (and in particular, exact histogram computation) requires $\Omega(n\log^{(t)}n)$ memory for some constant $t$ . In the full version of this paper, we generalize our algorithm to a larger number of passes.

Section 7: Summary

We conclude with a summary of our results and a discussion of open problems. In particular, we highlight the question of whether a separation between one-pass and multi-pass complexity exists also in the lower-accuracy regime $\varepsilon>1/\sqrt{n}$ .

3 Lower Bounds in the Low Error Regime

In this section, we prove the lower bounds in Theorems 1 and 2 in the $\varepsilon<1/\sqrt{n}$ regime. We first establish the communication complexity lower bound for computing set intersection size up to small additive error, and then show this result implies a lower bound for second-moment estimation in the streaming model under similar error guarantees. Throughout this section, we assume the universe $U$ is of large enough (yet polynomial) size in $n$ .

3.1 Approximate Set Intersection

Our proof follows the general framework of Dasgupta et al. [14], who proved a $\Omega(n\log n)$ lower bound for the one-way communication complexity of Set Disjointness. We begin by defining a promise problem that captures the essential hardness of approximate set intersection, which can be viewed as a refinement of the Gap Hamming Distance promise problem. We then construct, non-explicitly, a large family of inputs for Alice and a much smaller family for Bob such that, for every input in Alice’s family, the answers to the promise problem for all inputs in Bob’s family uniquely identifies it. Such a family implies a lower bound on the one-way communication complexity.

Definition 4 ( $\mathrm{INT}^{\varepsilon}$ ).

Let $X,Y\subset U$ inputs for Alice and Bob respectively, such that $|X|,|Y|\leq n$ . We denote by $\mathrm{INT}^{\varepsilon}(X,Y)$ the communication problem of calculating $|X\cap Y|$ up to an additive error $\varepsilon n$ with probability $>2/3$ .

Definition 5 ( $\text{INT-P}^{\alpha}$ Promise Problem).

Let $\alpha=\alpha(n)\in\left(\frac{1000}{\ln n},\frac{1}{2}\right)$ , and $X,Y\subset U$ inputs for Alice and Bob respectively, such that $|X|,|Y|\leq n$ .
We denote by $\emph{INT-P}^{\alpha}$ the communication problem of distinguishing with probability $>2/3$ between

$\blacksquare$

Yes-instances: Pairs $(X,Y)$ such that $|X\cap Y|\geq n^{1-\alpha}+\frac{1}{2}\sqrt{n^{1-\alpha}}$ .
$\blacksquare$

No-instances: Pairs $(X,Y)$ such that $|X\cap Y|\leq n^{1-\alpha}-\frac{1}{2}\sqrt{n^{1-\alpha}}$ .

For brevity, we write $(X,Y)\in\textsc{Yes}$ or $(X,Y)\in\textsc{No}$ , always referring to this promise problem.

We observe that any protocol solving $\mathrm{INT}^{\varepsilon}$ also solves $\mathrm{INT-P}^{\alpha}$ as long as $\varepsilon n<\frac{1}{2}\sqrt{n^{1-\alpha}}$ , or equivalently, $\alpha<\frac{\log\left({1}/\left({\varepsilon^{2}n}\right)\right)-2}{\log n}$ . We thus first establish an $\Omega(\alpha n\log n)$ lower bound for $\mathrm{INT-P}^{\alpha}$ and then deduce from it an $\Omega\left(n\log\left({1}/\left({\varepsilon^{2}n}\right)\right)\right)$ lower bound for $\mathrm{INT}^{\varepsilon}$ . We begin by constructing a large family $\mathcal{X}$ of possible inputs to Alice, and a small family $\mathcal{Y}$ for possible inputs to Bob, such that the answers to $\mathrm{INT-P}^{\alpha}$ on all inputs of $\mathcal{Y}$ uniquely identifies any input $X\in\mathcal{X}$ .

Definition 6 (Design).

A family $\mathcal{X}$ of subsets of $U$ is a design if:

$\blacksquare$

$\forall X\in\mathcal{X}$ , we have $|X|=n$ ,
$\blacksquare$

$\forall X\neq X^{\prime}\in\mathcal{X}$ , we have $|X\cap X^{\prime}|\leq\frac{n}{400}$ .

Definition 7 (Block-Uniform Distribution $\mathcal{D}_{n,\alpha}$ ).

Fix an integer $n\geq 1$ and a parameter $\alpha=\alpha(n)\in(\frac{1000}{\ln n},1)$ . Partition the universe $[n^{1+\alpha}]\subseteq U$ into $n$ disjoint blocks $B_{1},\dots,B_{n}$ , each of size $n^{\alpha}$ . The block-uniform distribution $\mathcal{D}_{n,\alpha}$ is the uniform distribution over sets $X\subset[n^{1+\alpha}],|X|=n$ obtained by the following sampling procedure:

1.

For each block $B_{i}$ independently, pick one element $x_{i}\in B_{i}$ uniformly at random.
2.

Output the set $X=\{x_{1},x_{2},\dots,x_{n}\}$ .

Lemma 8.

For a sufficiently large integer $n$ and any $\alpha=\alpha(n)\in(\frac{1000}{\ln n},\frac{1}{2})$ , there exists a design of size $\exp(c\cdot\alpha n\ln n)$ for some constant $c$ .

Proof.

We give a non-explicit construction using the probabilistic method. Independently and uniformly sample $N:=\exp\left(\frac{1}{3200}\alpha n\ln n\right)=\exp\left(c\cdot\alpha n\ln n\right)$ sets from $\mathcal{D}_{n,\alpha}$ .

Let $X,X^{\prime}$ be two sets sampled from $\mathcal{D}_{n,\alpha}$ . Let $Y\coloneqq|X\cap X^{\prime}|$ , and note that $Y\sim\text{Bin}(n,\frac{1}{n^{\alpha}})$ and $\mu\coloneqq\mathbb{E}[Y]=n\cdot\frac{1}{n^{\alpha}}=n^{1-\alpha}$ . Using a standard Chernoff bound we have

\Pr[Y\geq(1+\delta)\mu]\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}% \right)^{\mu},

with $(1+\delta)\mu=\frac{n}{400}$ , so $\delta=\frac{1}{400}n^{\alpha}-1$ . Note that as $\alpha\geq\frac{1000}{\ln n}$ , $\delta>0$ and the Chernoff bound can be applied. Thus, we deduce that

\ln\Pr\left[Y>\frac{n}{400}\right]\leq\mu\left(\delta-(1+\delta)\ln(1+\delta)% \right)\leq-\frac{1}{2}\mu\cdot\delta\ln(\delta),

where the last inequality follows as for all $\delta>0$ (which holds for all $\alpha$ when $n$ is sufficiently large), we have

\delta-(1+\delta)\ln(1+\delta)\leq-\frac{\delta\ln\delta}{2}.

Note that $\mu\delta=n^{1-\alpha}\bigl(\frac{n^{\alpha}}{400}-1\bigr)\geq\frac{n}{600}$ and $\ln\delta\geq\ln\bigl(\frac{n^{\alpha}}{600}\bigr)=\alpha\ln n-\ln 600$ . For all sufficiently large $n$ , this gives $\ln\delta\geq\frac{3}{4}\alpha\ln n$ . The constants here are arbitrary slack constants chosen to simplify the expressions. Hence,

\Pr\left[Y>\frac{n}{400}\right]\leq\exp\left(-\frac{\alpha n\ln n}{1600}\right).

We apply a union bound over all $\binom{N}{2}$ pairs of sets we sampled, and deduce that the probability that any pair had too big of an intersection is bounded by

\binom{N}{2}\cdot\exp\left(-\frac{1}{1600}\alpha n\ln n\right)<1.

Therefore, a design of the required size exists for $c=1/3200$ . $\hfill\blacktriangleleft$

Lemma 9 (Random $Y$ distinguishes between $X$ and $X^{\prime}$ ).

There exists a universal constant $p_{0}>0$ such that the following holds. Let $\alpha=\alpha(n)\in(\frac{1000}{\ln n},\frac{1}{2})$ and a design $\mathcal{X}$ , let $X\neq X^{\prime}\in\mathcal{X}$ be any pair from the design. Then, with $Y$ sampled uniformly from $\mathcal{D}_{n,\alpha}$ ,

\Pr_{Y}\left[((X,Y)\in\textsc{Yes}\wedge(X^{\prime},Y)\in\textsc{No})\vee((X,Y% )\in\textsc{No}\wedge(X^{\prime},Y)\in\textsc{Yes})\right]\geq p_{0}.

We call this event “ $Y$ distinguishes between $X$ and $X^{\prime}$ ".

Proof.

Let $p=n^{-\alpha}$ and $\mu=n^{1-\alpha}$ . Denote by $m=|X\cap X^{\prime}|\leq\frac{n}{400}$ and $M=n-m\geq\frac{399n}{400}$ , and denote $\mu_{M}=Mp,\mu_{m}=mp$ . We also denote

Z_{\text{same}}=|Y\cap X\cap X^{\prime}|,\quad Z_{\text{diff}}=|Y\cap(X% \setminus X^{\prime})|,\quad Z^{\prime}_{\text{diff}}=|Y\cap(X^{\prime}% \setminus X)|.

Z=|Y\cap X|=Z_{\text{same}}+Z_{\text{diff}},\quad Z^{\prime}=|Y\cap X^{\prime}% |=Z_{\text{same}}+Z^{\prime}_{\text{diff}}.

Note that as $X,X^{\prime},m,M$ are fixed (and are not random variables), and all probabilities are taken only over the random choice of $Y$ . Because the $m$ intersecting blocks and the $M$ differing blocks are disjoint and the choices of $Y$ values in each block are i.i.d, $Z_{\text{same}}$ is independent of $(Z_{\text{diff}},Z^{\prime}_{\text{diff}})$ .

Step 1: Chernoff bound for $Z_{\text{same}}$ .

We have $Z_{\text{same}}\sim\text{Bin}(m,p)$ with mean $\mu_{m}\leq\mu/400$ . Using a two-sided Chernoff bound with $\delta=\frac{2}{\sqrt{\mu_{m}}}$ we have

\Pr[|Z_{\text{same}}-\mu_{m}|>2\sqrt{\mu_{m}}]\leq 2e^{-4/3},\ \ \text{so}\ \ % \Pr[|Z_{\text{same}}-\mu_{m}|\leq 2\sqrt{\mu_{m}}]\geq c_{2}\coloneqq 1-2e^{-4% /3}>0.47.

Step 2: Berry–Esseen tail bound for $Z_{\mathrm{diff}}$ and $Z^{\prime}_{\mathrm{diff}}$ .

Fix an arbitrary ordering of the $M$ “differing” blocks and write

B_{i}=\mathds{1}\{Y\cap X^{\prime}\text{ is not empty in block }i\}\quad i=1,% \dots,M.

Then $B_{i}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}\mathrm{Ber}(p)$ and $Z^{\prime}_{\mathrm{diff}}=\sum_{i=1}^{M}B_{i}$ . Center the variables by setting $V_{i}:=B_{i}-p$ and $S_{M}:=\sum_{i=1}^{M}V_{i}$ , so that $Z^{\prime}_{\mathrm{diff}}=\mu_{M}+S_{M}$ .

Verifying the Berry–Esseen assumptions. Each $V_{i}$ satisfies $\mathbb{E}[V_{i}]=0$ , $\sigma^{2}:=\operatorname{Var}(V_{i})=p(1-p)>0$ , and $\rho:=\mathbb{E}[|V_{i}|^{3}]=p\cdot(1-p)^{3}+(1-p)\cdot p^{3}=p(1-p)\left((1-% p)^{2}+p^{2}\right)\leq p(1-p)=\sigma^{2}$ .

Normalisation. Let $\sigma_{M}^{2}=\operatorname{Var}(S_{M})=Mp(1-p)=\mu_{M}(1-p)$ and denote by $\widehat{S}_{M}:=S_{M}/\sigma_{M}$ which has cumulative distribution function $F_{M}(x)=\Pr[\widehat{S}_{M}\leq x]$ .

Berry–Esseen inequality. By the Berry-Esseen Inequality [15, Ch. XVI, §5, Thm. 1] with the sharpened constant of Shevtsova $C=0.4748$ [32], where $\Phi$ denotes the standard normal CDF, we have

|F_{M}(x)-\Phi(x)|\leq\frac{C\rho}{\sigma^{3}\sqrt{M}}=\frac{C}{\sqrt{Mp(1-p)}% }=\frac{C}{\sqrt{\mu_{M}(1-p)}}\leq\frac{\sqrt{2}C}{\sqrt{\mu_{M}}},

where the last inequality holds as $1-p>1/2$ .

Applying the bound. We want a lower bound for $\Pr[Z^{\prime}_{\mathrm{diff}}\leq\mu_{M}-0.603\sqrt{\mu_{M}}]$ . Put $k=\mu_{M}-0.603\sqrt{\mu_{M}}$ and $x_{*}=(k-\mu_{M})/\sigma_{M}=-0.603/\sqrt{1-p}\in(-0.853,-0.603)$ . Because $\Phi$ is decreasing, $\Phi(x_{*})\geq\Phi(-0.603)=0.2736$ . Applying (BE) and assuming that $n$ is large enough so $\mu_{M}\geq 100$ ,

\Pr\bigl[Z^{\prime}_{\mathrm{diff}}\leq\mu_{M}-0.603\sqrt{\mu_{M}}\bigr]=F_{M}% (x_{*})\geq\Phi(x_{*})-\frac{\sqrt{2}\cdot 0.4748}{\sqrt{\mu_{M}}}\geq 0.2736-% 0.067>0.2.

Hence,

\Pr\left[Z^{\prime}_{\mathrm{diff}}\leq\mu_{M}-0.603\sqrt{\mu_{M}}\right]\geq c% _{1}:=0.2.

By symmetry the same constant bound holds for $\Pr\bigl[Z_{\mathrm{diff}}\geq\mu_{M}+0.603\sqrt{\mu_{M}}\bigr]$ .

Step 3: Combining bounds.

Let $R:=\mu_{M}+0.603\sqrt{\mu_{M}}$ and $L:=\mu_{M}-0.603\sqrt{\mu_{M}}$ . When all three of the above events hold, we get

Z\geq R+Z_{\text{same}}\geq\mu+0.5\sqrt{\mu},\quad Z^{\prime}\leq L+Z_{\text{% same}}\leq\mu-0.5\sqrt{\mu}.

Which implies

	$\displaystyle\Pr\left[(Z\geq\mu+0.5\sqrt{\mu})\wedge(Z^{\prime}\leq\mu-0.5% \sqrt{\mu})\right]\geq$
	$\displaystyle\Pr\Big[(Z_{\text{diff}}\geq R)\wedge(Z^{\prime}_{\text{diff}}% \leq L)\wedge(Z_{\text{same}}\in\left[\mu_{m}-2\sqrt{\mu_{m}},\mu_{m}+2\sqrt{% \mu_{m}})\right]\Big]$
	$\displaystyle=\Pr\left[(Z_{\text{diff}}\geq R)\wedge(Z^{\prime}_{\text{diff}}% \leq L)\right]\cdot\Pr\left[Z_{\text{same}}\in\left[\mu_{m}-2\sqrt{\mu_{m}},% \mu_{m}+2\sqrt{\mu_{m}})\right]\right],$

where the last equality holds as $Z_{same}$ is independent from $Z_{diff}$ and $Z^{\prime}_{diff}$ .

Step 4: Negative correlation between $Z_{diff}$ and $Z^{\prime}_{diff}$ .

For every differing index $i$ define the indicators $E_{i}=\mathds{1}\{Y_{i}=X_{i}\}$ and $F_{i}=\mathds{1}\{Y_{i}\neq X^{\prime}_{i}\}$ . Because the random choice of $Y$ is block-wise independent, the collection $\{(E_{i},F_{i})\}_{i=1}^{M}$ is also independent. Consider the two increasing events

A:=\Bigl\{\sum_{i}E_{i}\geq\mu_{M}+0.603\sqrt{\mu_{M}}\Bigr\},\qquad B:=\Bigl% \{\sum_{i}(1-F_{i})\leq\mu_{M}-0.603\sqrt{\mu_{M}}\Bigr\}.

Since $E_{i}=1$ implies $F_{i}=1$ , both $A$ and $B$ are monotone in the same direction. By the Harris (binary FKG) inequality [19] we thus have

\Pr[A\wedge B]\geq\Pr[A]\Pr[B].

Rewriting $A$ and $B$ in terms of $Z_{\mathrm{diff}}$ and $Z^{\prime}_{\mathrm{diff}}$ gives

	$\displaystyle\Pr\bigl[Z_{\mathrm{diff}}\geq\mu_{M}+0.603\sqrt{\mu_{M}}\wedge Z% ^{\prime}_{\mathrm{diff}}\leq\mu_{M}-0.603\sqrt{\mu_{M}}\bigr]$
	$\displaystyle\geq\Pr[Z_{\mathrm{diff}}\geq\mu_{M}+0.603\sqrt{\mu_{M}}]\cdot\Pr% [Z^{\prime}_{\mathrm{diff}}\leq\mu_{M}-0.603\sqrt{\mu_{M}}]\geq c_{1}^{2}.$

Step 5: Symmetry.

Swapping $X$ and $X^{\prime}$ gives a disjoint event of equal probability. So the total distinguishing probability is at least

\Pr[Y\text{ distinguishes }X,X^{\prime}]\geq 2c_{1}^{2}c_{2}=:p_{0}>0.\

$\hfill\blacktriangleleft$

Lemma 10 (Existence of family $\mathcal{Y}$ fully distinguishing a design $\mathcal{X}$ ).

Let $\alpha=\alpha(n)\in(\frac{1000}{\ln n},\frac{1}{2})$ , and let $\mathcal{X}$ be a design of size $\exp(c\cdot\alpha n\ln n)$ . There exists a family $\mathcal{Y}\subseteq U$ such that:

$\blacksquare$

$|Y|=n$ for all $Y\in\mathcal{Y}$ .
$\blacksquare$

$|\mathcal{Y}|\leq k\cdot\alpha n\ln n$ for a universal constant $k$ .
$\blacksquare$

For any $X\neq X^{\prime}\in\mathcal{X}$ , some $Y\in\mathcal{Y}$ distinguishes them.

We call this behavior $\mathcal{Y}$ describes $\mathcal{X}$ .

Proof.

We draw a set $\mathcal{Y}$ of the desired size uniformly and independently from $\mathcal{D}_{n,\alpha}$ . Note that the amount of pairs $X\neq X^{\prime}\in\mathcal{X}$ is smaller than $\exp(c\cdot\alpha n\ln n)^{2}=\exp(2c\cdot\alpha n\ln n)$ . As described in Lemma 9, for some $X\neq X^{\prime}$ , the probability that a single $y\in\mathcal{Y}$ distinguishes between $X$ and $X^{\prime}$ is at least $p_{0}$ , (where $p_{0}$ is the constant probability bound from Lemma 9). As the sets in $\mathcal{Y}$ are chosen independently,

\mathbb{P}\left[\forall Y\in\mathcal{Y},\text{$Y$ does not distinguish between% $X$ and $X^{\prime}$}\right]<(1-p_{0})^{|\mathcal{Y}|}.

Therefore, by a union bound,

	$\displaystyle\mathbb{P}\left[\exists X\neq X^{\prime}\in\mathcal{X}:\forall Y% \in\mathcal{Y},\text{$Y$ does not distinguish between $X$ and $X^{\prime}$}\right]$
	$\displaystyle\qquad<\exp(2c\cdot\alpha n\ln n)\cdot(1-p_{0})^{\|\mathcal{Y}\|},$

and for $|\mathcal{Y}|>\underbrace{-\frac{2c}{\ln(1-p_{0})}}_{k}\cdot\alpha n\ln{n}$ , this probability is smaller than 1. Meaning, when randomly choosing $\mathcal{Y}$ of size $k\alpha\cdot n\ln{n}$ , the probability that it differentiates between every pair $X\neq X^{\prime}\in\mathcal{X}$ is positive. Therefore, by the probabilistic method, a family $\mathcal{Y}$ that meets the conditions exist. $\hfill\blacktriangleleft$

We are now ready to prove the desired lower bound.

Lemma 11.

For any large enough $n$ , and for any $\varepsilon<1/(2e^{500}\sqrt{n})$ , the randomized one-way communication complexity of $\emph{INT}^{\varepsilon}$ is $\Omega(n\log(1/\varepsilon^{2}n))$ .

Proof.

Any algorithm that solves $\operatorname{INT}^{\varepsilon}$ with probability $>2/3$ can be amplified to fail with probability at most $\delta$ for any constant $\delta$ by repetition. We thus assume the algorithm has a small enough failure probability, to be specified later. Denote by $\alpha=\alpha(n):=\frac{\log\left({1}/\left({\varepsilon^{2}n}\right)\right)-2% }{\log n}$ . For this choice, $\varepsilon n<\frac{1}{2}\sqrt{n^{1-\alpha}}$ , and thus an algorithm that solves $\operatorname{INT}^{\varepsilon}$ can easily be used to solve $\operatorname{INT\text{-}P}^{\alpha}$ . Note that for $n^{-3/4}<\varepsilon<1/(2e^{500}\sqrt{n})$ we have $\frac{1000}{\ln n}<\alpha<\tfrac{1}{2}$ . We may ignore the range $\varepsilon\leq n^{-3/4}$ as for $\varepsilon=2n^{-3/4}$ we already we get a lower bound of $\Omega(n\log n)$ which matches the upper bound even for $\varepsilon=0$ .

By Lemma 8, there exists a design $\mathcal{X}$ of size $\exp(c\cdot\alpha n\ln n)$ . By Lemma 10, there exists some set-family $\mathcal{Y}$ of size $k\cdot\alpha n\ln n$ that describes $\mathcal{X}$ . Consider the input distribution in which Alice gets a random set $X$ from $\mathcal{X}$ and Bob gets a random set $Y$ from $\mathcal{Y}$ . Applying Yao’s minimax principle [36], it suffices to lower-bound the distributional one-way communication complexity of any deterministic protocol that fails on this distribution with probability less than $\delta$ .

As $|\mathcal{X}|=\exp(c\alpha n\ln n)$ , a uniformly sampled $X\in\mathcal{X}$ has entropy

H(X)=\log_{2}|\mathcal{X}|=\frac{c\alpha n\ln n}{\ln 2},

and for simplicity we modify the constant $c$ to “absorb” the factor $\frac{1}{\ln 2}$ . By Lemma 10, the sequence $\{\operatorname{INT-P}^{\alpha}(X,y):y\in\mathcal{Y}\}$ uniquely determines $X$ , therefore

H\left(\{\operatorname{INT-P}^{\alpha}(X,y)\}_{y\in\mathcal{Y}}\right)\geq H(X% )\geq c\cdot\alpha n\ln n.

Let $A(X)$ be the message sent by Alice in a deterministic one-way protocol. Let $\delta$ be small enough that $\delta<1/3$ and $H(\delta)<\frac{c}{2k}$ , and let $t=|\mathcal{Y}|=k\alpha n\ln n$ . Then,

$\displaystyle H(\delta)$	$\displaystyle\geq H(\operatorname{INT-P}^{\alpha}(X,Y)\mid A(X),Y)\quad$	by Fano’s inequality
	$\displaystyle=\frac{1}{t}\sum_{y\in\mathcal{Y}}H(\operatorname{INT-P}^{\alpha}% (X,y)\mid A(X),Y=y)$
	$\displaystyle=\frac{1}{t}\sum_{y\in\mathcal{Y}}H(\operatorname{INT-P}^{\alpha}% (X,y)\mid A(X))\quad$	since $X\perp Y$
	$\displaystyle\geq\frac{1}{t}H\left(\{\operatorname{INT-P}^{\alpha}(X,y)\}_{y% \in\mathcal{Y}}\mid A(X)\right)\quad$	by sub-additivity
	$\displaystyle=\frac{1}{t}\left(H\left(\{\operatorname{INT-P}^{\alpha}(X,y)\}_{% y\in\mathcal{Y}}\right)-H(A(X))\right)\quad$	by the chain rule
	$\displaystyle\geq\frac{1}{t}\left(H\left(\{\operatorname{INT-P}^{\alpha}(X,y)% \}_{y\in\mathcal{Y}}\right)-\|A(X)\|\right).$

Rearranging, we have that the message size is at least

|A(X)|\geq H\left(\{\operatorname{INT-P}^{\alpha}(X,y)\}_{y\in\mathcal{Y}}% \right)-tH(\delta).

Since $H\left(\{\operatorname{INT-P}^{\alpha}(X,y)\}_{y\in\mathcal{Y}}\right)=H(X)% \geq c\cdot\alpha n\ln n$ and $tH(\delta)<\frac{c}{2}\alpha n\ln n$ , we get,

|A(X)|\geq\frac{c}{2}\cdot\alpha n\ln n=\Omega(\alpha n\ln n)=\Omega(n\log(1/% \varepsilon^{2}n)).\

$\hfill\blacktriangleleft$

3.2 Second Moment Estimation

Corollary 12.

The space complexity of $\left(1\pm\varepsilon\right)$ -estimating the second frequency moment of a stream of $n$ elements from $U$ , for any $\frac{1}{n^{2}}\leq\varepsilon\leq\frac{1}{2e^{500}\sqrt{n}}$ , is

\Omega\left(n\log\left(\frac{1}{\varepsilon^{2}n}\right)\right).

Proof.

Given a streaming algorithm that $(1\pm\varepsilon)$ -estimates $F_{2}$ using $s$ bits of memory, we obtain a one-way communication protocol for $\operatorname{INT}^{2\varepsilon}$ that uses $s+O(\log n)$ bits.

Alice feeds her set $X$ (each element once) into the streaming algorithm, obtaining memory image $M$ . She sends $(M,|X|)$ to Bob. Bob resumes the algorithm on his set $Y$ , obtains an output $Z$ , and returns

m=\frac{Z-|X|-|Y|}{2}.

Let $S$ be the concatenation of $X$ followed by $Y$ . Each element in $X\triangle Y$ has frequency 1 in $S$ , each element in $X\cap Y$ frequency 2, so

F_{2}(S)=|X\triangle Y|+4|X\cap Y|=|X|+|Y|+2|X\cap Y|.

The above implies that $F_{2}\leq 4n$ , hence $|Z-F_{2}(S)|\leq F_{2}(S)\varepsilon\leq 4\varepsilon n$ , which in turn gives

|m-|X\cap Y||=\frac{1}{2}|Z-F_{2}(S)|\leq 2\varepsilon n.

Thus the protocol computes $\operatorname{INT}^{2\varepsilon}$ with the same success probability as the $F_{2}$ estimator (say $2/3$ ), using $s+O(\log n)$ bits. Applying Theorem 11 now yields the claimed streaming lower bound for $F_{2}$ . $\hfill\blacktriangleleft$

4 Upper Bounds in the Low Error Regime

In this section we present matching upper bounds to the lower bounds established in the previous section, for both problems of interest: approximate set intersection in the one-way communication model, and second-moment estimation in the streaming model. These results establish the upper bounds required for Theorems 1 and 2 in the $\varepsilon<1/\sqrt{n}$ regime.

4.1 Second Moment Estimation

Lemma 13.

Let $n$ be large enough, $1/n^{2}\leq\varepsilon\leq 1/\sqrt{n}$ , and $U$ a set of size $|U|=\text{poly}(n)$ . Then, we can $(1\pm\varepsilon)$ -estimate the second frequency moment of a stream of $n$ elements from $U$ , with probability larger than $99\%$ , using space

O\left(n\log\left(\frac{1}{\varepsilon^{2}n}\right)\right).

We first observe that any unordered multiset of $n$ elements from a universe of size $m$ can be stored using $\log{\binom{n+m-1}{n}}=O\left(n\log\left(2+\frac{m}{n}\right)\right)$ bits of space. This immediately implies, for example, the $O\left(n\log\frac{|U|}{n}\right)$ upper bound when $|U|\geq 2n$ . The algorithm we present to prove Lemma 13 is rather natural: we choose $m\approx\varepsilon^{-2}$ and draw a hash function $h:U\rightarrow[m]$ that maps our element universe to a smaller one, and then maintain exactly the image of the input stream through $h$ . Finally, we directly compute the $F_{2}$ of the stream. When $\varepsilon\approx 1/\sqrt{n}$ and hence $m\approx n$ , and thus, our hash table is expected to contain roughly $\Theta(n^{2}/m)\approx\Theta(n)$ hash collisions. The crucial observation is that, as we only care about the number of (actual) collisions in the table, we may subtract from it the expected number of hash collisions and thus vastly reduce the error caused by the hashing.

Algorithm $\mathcal{A}$

$\blacksquare$

Denote by $m:=\lceil\frac{201}{\varepsilon^{2}}\rceil$ .
$\blacksquare$

Draw a hash function $h:U\rightarrow[m]$ from a $4$ -wise independent hash family, and store it in memory.
$\blacksquare$

When receiving the elements of the stream $S$ , maintain in memory the exact multiset $h(S)$ of images of stream elements through $h$ .
$\blacksquare$

Finally, directly compute $F:=F_{2}\left(h\left(S\right)\right)$ the second frequency moment of the maintained multiset, then output $F^{\prime}:=\frac{m}{m-1}\cdot\left(F-\frac{n^{2}}{m}\right)$ .

We note that the space complexity of $\mathcal{A}$ is as desired, as $h$ can be stored using $O(\log n)$ bits of memory and the multiset $h(S)$ using $O\left(n\log\left(2+\frac{m}{n}\right)\right)$ bits of space.

Claim 14.

$\mathbb{E}\left[F^{\prime}\right]=F_{2}(S)$ .

Proof.

Denote by $x_{1},\ldots,x_{n}$ the elements of the stream $S$ . Denote by $X_{i,j}$ the event that $h(x_{i})=h(x_{j})$ . We have $F=\sum_{i,j\in[n]}X_{i,j}$ . We observe that if $x_{i}=x_{j}$ then $Pr(X_{i,j})=1$ , and if $x_{i}\neq x_{j}$ then $Pr(X_{i,j}=1)=\frac{1}{m}$ . By linearity of expectation we thus have $\mathbb{E}\left[F\right]=F_{2}(S)+\left(n^{2}-F_{2}\left(S\right)\right)\cdot% \frac{1}{m}$ and in turn $\mathbb{E}[F^{\prime}]=F_{2}(S)$ . $\hfill\vartriangleleft$

Claim 15.

$Var(F^{\prime})\leq\frac{1}{100}\cdot\left(\varepsilon F_{2}\left(S\right)% \right)^{2}$ .

Proof.

We begin by bounding $Var(F)$ . Denote by $P:=\{(i,j)\in[n]^{2}|x_{i}=x_{j}\}$ the set of $F_{2}(S)$ pairs of indices such that the two corresponding stream elements are equal. Denote by ${P}^{C}=[n]^{2}\setminus P$ all other indices. We have

	$\displaystyle\mathbb{E}\left[F^{2}\right]$	$\displaystyle=\mathbb{E}\left[\left(\sum_{(i,j)\in[n]^{2}}X_{i,j}\right)^{2}\right]$
		$\displaystyle=\mathbb{E}\left[\left(\sum_{(i,j)\in P}X_{i,j}\right)^{2}+2\left% (\sum_{(i,j)\in P}X_{i,j}\right)\left(\sum_{(i,j)\in P^{C}}X_{i,j}\right)+% \left(\sum_{(i,j)\in P^{C}}X_{i,j}\right)^{2}\right]$
		$\displaystyle=F_{2}(S)^{2}+2F_{2}(S)\cdot\mathbb{E}\left[\sum_{(i,j)\in P^{C}}% X_{i,j}\right]+\mathbb{E}\left[\left(\sum_{(i,j)\in P^{C}}X_{i,j}\right)^{2}\right]$
		$\displaystyle=F_{2}(S)^{2}+2F_{2}(S)\cdot\left(n^{2}-F_{2}(S)\right)\cdot\frac% {1}{m}+\mathbb{E}\left[\left(\sum_{(i,j)\in P^{C}}X_{i,j}\right)^{2}\right].$

Let $(i,j),(k,\ell)\in P^{C}$ . Note that $x_{i}\neq x_{j}$ and $x_{k}\neq x_{\ell}$ . The set $I:=\{x_{i},x_{j},x_{k},x_{\ell}\}$ can thus be of size $2$ , $3$ , or $4$ . If its size is $|I|=2$ , then $Pr(X_{i,j}X_{k,\ell})=\frac{1}{m}$ . Also, without loss of generality $x_{i}=x_{k},x_{j}=x_{\ell}$ and thus $(i,k),(j,\ell)\in P$ . In particular, there are at most $2|P|^{2}$ such pairs. If $|I|\in\{3,4\}$ , then $Pr(X_{i,j}X_{k,\ell})=\frac{1}{m^{2}}$ . We therefore have

\mathbb{E}\left[\left(\sum_{(i,j)\in P^{C}}X_{i,j}\right)^{2}\right]\leq 2|P|^% {2}\cdot\frac{1}{m}+|P^{C}|^{2}\cdot\frac{1}{m^{2}}=2F_{2}(S)^{2}\cdot\frac{1}% {m}+\left(n^{2}-F_{2}\left(S\right)\right)^{2}\cdot\frac{1}{m^{2}}.

Combining the inequalities above we deduce

Var(F)=\mathbb{E}[F^{2}]-\mathbb{E}[F]^{2}\leq 2F_{2}(S)^{2}\cdot\frac{1}{m}% \leq\frac{2}{201}\cdot\left(\varepsilon F_{2}\left(S\right)\right)^{2}.

We conclude that

Var(F^{\prime})=\left(\frac{m}{m-1}\right)^{2}\cdot Var(F)\leq\frac{1}{100}% \cdot\left(\varepsilon F_{2}\left(S\right)\right)^{2},

for any sufficiently large $n$ (and in turn $m$ ). $\hfill\vartriangleleft$

We conclude the proof of Lemma 13 by using Chebyshev’s inequality. ∎

4.2 Approximate Set Intersection

Corollary 16.

For any $\varepsilon<1/\sqrt{n}$ , the randomized one-way communication complexity of $\emph{INT}^{\varepsilon}$ is $O(n\log(1/\varepsilon^{2}n))$ .

Proof.

By the same argument as in Corollary 12, any algorithm that $(1\pm\varepsilon)$ -estimates $F_{2}$ can be converted to a communication algorithm solving $\operatorname{INT}^{2\varepsilon}$ with the same success probability, at an added communication cost of $O(\log n)$ , which doesn’t change the asymptotic communication bound and implies the desired upper bound. $\hfill\blacktriangleleft$

5 Approximate Set Intersection in the High Error Regime

In this section, we establish a tight $\Theta(1/\varepsilon^{2}+\log n)$ bound on the communication complexity of the approximate set intersection problem, for both the one-way and two-way communication models. Combined with the results from the low-error regime, these bounds complete the proof of Theorem 2.

5.1 Lower Bound

Lemma 17.

Let $\varepsilon>1/\sqrt{n}$ . The randomized communication complexity of $\operatorname{INT}^{\varepsilon}$ is $\Omega\left(\frac{1}{\varepsilon^{2}}\right)$ .

Proof.

We show a reduction from the Gap Hamming Distance (GHD) communication problem. In GHD, Alice and Bob receive binary strings $x\in\{0,1\}^{k}$ and $y\in\{0,1\}^{k}$ respectively, and output (with probability $>2/3$ ) “Yes” if $\Delta(x,y)<\frac{1}{2}k-\sqrt{k}$ , “No” if $\Delta(x,y)>\frac{1}{2}k+\sqrt{k}$ , and any answer is acceptable if neither condition holds (where $\Delta$ denotes the Hamming distance). Chakrabarti and Regev ([13]) proved that any randomized protocol solving GHD requires $\Omega(k)$ bits of communication, even with two-way communication.

Let $k=1/\varepsilon^{2}$ and let $x,y\in\{0,1\}^{k}$ be some input to GHD. Assume, without loss of generality, that $k\mid n$ (otherwise pad $n$ up to the next multiple of $k$ ). We construct two sets $A^{\prime},B^{\prime}$ as follows,

	$\displaystyle A^{\prime}$	$\displaystyle:=\bigcup_{i=0}^{k-1}\Bigl\{\bigl(x_{i}\cdot n+i\cdot\frac{n}{k}+% t\bigr)\Bigm\|0\leq t<\frac{n}{k}\Bigr\},$
	$\displaystyle B^{\prime}$	$\displaystyle:=\bigcup_{i=0}^{k-1}\Bigl\{\bigl(y_{i}\cdot n+i\cdot\frac{n}{k}+% t\bigr)\Bigm\|0\leq t<\frac{n}{k}\Bigr\}.$

Each coordinate $i$ of the GHD strings is “blown up” into a block of $\frac{n}{k}$ distinct elements. Hence, $A^{\prime},B^{\prime}\subset\left[2n\right],|A^{\prime}|=|B^{\prime}|=n$ , and for every $i$ the two blocks are equal (meaning, they contribute $n/k$ to the intersection size) iff $x_{i}=y_{i}$ . Note that

	$\displaystyle\Delta(x,y)<\frac{k}{2}-\sqrt{k}$	$\displaystyle\implies\|A^{\prime}\cap B^{\prime}\|=n-\frac{n}{k}\Delta(x,y)$
		$\displaystyle>\frac{n}{2}+\sqrt{k}\cdot\frac{n}{k}=\frac{n}{2}+\varepsilon n% \qquad\text{(``Yes'' instance)},$
	$\displaystyle\Delta(x,y)>\frac{k}{2}+\sqrt{k}$	$\displaystyle\implies\|A^{\prime}\cap B^{\prime}\|=n-\frac{n}{k}\Delta(x,y)$
		$\displaystyle<\frac{n}{2}-\sqrt{k}\cdot\frac{n}{k}=\frac{n}{2}-\varepsilon n% \qquad\text{(``No'' instance)}.$

Let $\Pi(A^{\prime},B^{\prime})$ be some communication protocol that solves $\operatorname{INT}^{\varepsilon}$ . The following algorithm will hence solve GHD: Alice calculates $A^{\prime}$ and Bob calculates $B^{\prime}$ , then they run $\Pi(A^{\prime},B^{\prime})$ and answer “Yes” iff $\Pi(A^{\prime},B^{\prime})$ outputs anything larger than $n/2$ . As shown above, if the GHD answer is “Yes”, this will indeed be the case, and if the GHD answer is “No”, it will not. As the only communication required by this protocol is the one required by $\Pi$ , by the above, $\Pi$ requires $\Omega(k)=\Omega(1/\varepsilon^{2})$ bits of communication. $\hfill\blacktriangleleft$

Similarly, a reduction from Equality yields a lower bound of $\Omega(\log n)$ for private-randomness two-way communication protocols, even when $\varepsilon$ is constant: encode each input as a distinct block of size $2\varepsilon n+1$ , so equal inputs give intersection size $2\varepsilon n+1$ and unequal inputs give intersection size $0$ .

5.2 Upper Bound

Lemma 18.

Let $\varepsilon>1/\sqrt{n}$ . The one-way randomized communication complexity of $\operatorname{INT}^{\varepsilon}$ is $O\left(\frac{1}{\varepsilon^{2}}\right)$ in the public-randomness model, and $O\left(\frac{1}{\varepsilon^{2}}+\log n\right)$ in the private-randomness model.

Proof.

We work in the public-randomness model and remark the changes needed for private-randomness at the end. We present three solutions, each improving on the last.

Algorithm 1 (One-way, $O((\log n)/\varepsilon^{2})$ bits).

Define $p=\frac{c}{n\varepsilon^{2}},c=40$ . Alice samples $A^{\prime}\subset A$ such that $\forall a_{i}\in A:a_{i}\in A^{\prime}$ with probability $p$ , independently. If $|A^{\prime}|\geq 10p|A|$ , the algorithm aborts, which by Markov’s inequality happens with probability $<0.1$ . Otherwise, Alice sends $(|A|,A^{\prime})$ . Bob outputs $\frac{1}{p}\cdot|A^{\prime}\cap B|$ .
Correctness: Denote $C=A\cap B,C^{\prime}=A^{\prime}\cap B$ , and note that $\forall c\in C:\Pr[c\in C^{\prime}]=p$ . Denote $m=|C|,m^{\prime}=|C^{\prime}|$ . As $\mathbb{E}[m^{\prime}]=mp$ , and $\operatorname{Var}[m^{\prime}]\leq mp$ , by Chebyshev’s inequality,

\Pr\left[\left|\frac{1}{p}m^{\prime}-m\right|\geq\frac{\varepsilon n}{2}\right% ]=\Pr\left[\left|m^{\prime}-pm\right|\geq\frac{\varepsilon np}{2}\right]\leq% \frac{\operatorname{Var}[m^{\prime}]}{\varepsilon^{2}n^{2}p^{2}/4}\leq\frac{4% mp}{\varepsilon^{2}n^{2}p^{2}}\leq\frac{4}{c}\leq\frac{1}{10}

By a union bound, the algorithm fails with probability $<0.2$ .
Communication cost: Each element in $A^{\prime}$ can be written using $O(\log n)$ bits, and $|A|$ is $\log n$ bits long. As $|A^{\prime}|$ is bounded by $10p|A|\leq 10c/\varepsilon^{2}$ , the communication cost is $O(\log n/\varepsilon^{2})$ .

Algorithm 2 (Two-way, $O(1/\varepsilon^{2})$ bits).

Reusing the notations from Algorithm 1, we replace the method for sampling $A^{\prime}$ : Alice and Bob, interpret their shared randomness as a random hash function $h:U\rightarrow[n]$ . Using $h$ , they construct the samples,

A^{\prime}=\{a\in A:h(a)\leq pn\},\qquad B^{\prime}=\{b\in B:h(b)\leq pn\}.

We note that $C^{\prime}=A^{\prime}\cap B=A^{\prime}\cap B^{\prime}$ as any element in the intersection is either in both samples or neither. Therefore, as before, $\Pr[c\in C^{\prime}]=p=\Pr[c\in A^{\prime}\cap B^{\prime}]$ . If $A^{\prime}$ or $B^{\prime}$ have size $\geq 10c/\varepsilon^{2}$ , the algorithm aborts, which happens with probability $<0.2$ by the same analysis as above. After constructing the two sets, Alice and Bob run a two-way communication algorithm for computing $|A^{\prime}\cap B^{\prime}|$ exactly using $O(|A^{\prime}|+|B^{\prime}|)$ bits of communication and fails with probability at most $0.01$ , e.g. using the protocol of Brody et al. [11]. As both sets are of size $O(1/\varepsilon^{2})$ , this is also the required communication. As before, they output $\frac{1}{p}m^{\prime}=\frac{1}{p}|A^{\prime}\cap B^{\prime}|$ , which is a correct response with probability $>0.9$ . Therefore, the algorithm fails with probability $<0.31<1/3$ , as claimed.

Algorithm 3 (One-way, $O(1/\varepsilon^{2})$ bits).

We construct $A^{\prime},B^{\prime}$ as in Algorithm 2, but replace the two-way intersection sub-routine by the one-way estimator presented in Corollary 12, that computes the same intersection size up to a small additive error: For $k=\Theta(\frac{1}{\varepsilon^{2}})$ , with $O(k)$ transmitted bits it outputs $z\approx|A^{\prime}\cap B^{\prime}|$ up to an additive error $\frac{\varepsilon}{200}k=\Theta(1/\sqrt{k})\cdot k$ , and fails with probability $<0.01$ . As Algorithms 1 and 2 gave an error $<\frac{1}{2}\varepsilon n$ , the triangle inequality shows we end up with error $<\varepsilon n$ if both Algorithm 2 and the sub-routine succeed. The overall failure probability is thus $<0.2+0.1+0.01=0.31<1/3$ .

Private randomness.

Newman’s Theorem [29] replaces shared randomness by private randomness at an additive cost of $O(\log n)$ bits, resulting in $O(1/\varepsilon^{2}+\log n)$ . $\hfill\blacktriangleleft$

6 Multipass Histogram Streaming

In this section we present a two-pass streaming algorithm that, with high probability, computes the exact histogram using $O(n\log\log n)$ bits of space. Afterwards, we consider streaming algorithms with a constant number of passes $r$ and show that, for any fixed constant $r$ , $\Theta\!\bigl(n\log^{(\Theta(r))}\!n\bigr)$ bits of memory are both necessary and sufficient for exact histogram computation.

6.1 Two–Pass Algorithm

Our approach is inspired by the two-way communication protocol of Brody et al. [11] for computing exact set intersection, which repeatedly verifies the equality of large sets and invokes a more expensive local-refinement step only when a set fails verification. While such verification is straightforward in the communication setting (each party has full access to its input), our main contribution is to design an analogous mechanism that operates efficiently in the streaming model.

At a high level, the algorithm partitions the stream into buckets via hashing and constructs compact approximate histograms using short fingerprints rather than full element identities. Most of these histograms are correct, and errors arise only from the small number of fingerprint collisions. A simpler three-pass warmup version of this framework appears in the full version.

The main idea of the two-pass algorithm is to avoid correcting buckets individually. Instead, we define a single global discrepancy polynomial that captures all over- and under-counts simultaneously. Since only a small number of coefficients of this polynomial can be non-zero, sparse-recovery ideas allow us to reconstruct it with high probability, and then directly correct the affected histogram entries.

Lemma 19.

Let $S=\langle x_{0},\dots,x_{T-1}\rangle$ be a stream of $T\leq n$ elements drawn from a universe $U$ . There is a two-pass streaming algorithm that outputs the exact histogram of $S$ using $O\bigl(n\log\log n\bigr)$ bits of memory and succeeds with probability at least $1-\frac{3}{n^{2}}$ .

Preliminaries

We use the following hash functions throughout this section.

$\blacksquare$

$b:U\rightarrow\left[\frac{n}{\log n}\right]$ is a $6\log n$ -wise independent hash function. We refer to all elements with value $j$ in $b$ as the $j$ -th bucket.
$\blacksquare$

$\forall j\in\left[\frac{n}{\log n}\right],g_{j}:U\rightarrow[2^{10\log\log n}]$ is a pairwise independent hash function. We refer to $g_{b(x_{i})}(x_{i})$ as the fingerprint of $x_{i}$ .

Definition 20.

Let $\mathcal{D}$ denote the family of multi-linear polynomials $\delta(z_{x_{1}},\dots,z_{x_{|U|}})$ with at most $6n/(\log n)^{5}$ non-zero coefficients, where all coefficients are integers in $[-n,n]$ .

The algorithm

Pass 1 (fingerprint histograms)

For every bucket $j\in[n/\log n]$ , initialize an empty histogram $H_{j}$ . The structure of the histograms is a list of pairs, each containing a fingerprint and a counter of appearances of this fingerprint in this bucket. When an element $x_{i}$ arrives, we check if $g_{b(x_{i})}(x_{i})$ was already encountered in bucket $b(x_{i})$ . If it is new, we add it to the histogram with counter $1$ . If it is not new, we increment the respective counter. We use the notation $H_{j}[y]$ for the number of appearances of fingerprint $y$ in the $j$ -th bucket.

Pass 2 (sparse recovery)

Choose a prime $q$ with $3^{n}<q<2\cdot 3^{n}$ and pick a random hash function $h:U\rightarrow\mathbb{F}_{q}$ .

For each index $i$ let $first(x_{i})$ be the first stream element $x_{\ell}$ such that $b(x_{\ell})=b(x_{i})$ and $fingerprint(x_{\ell})=fingerprint(x_{i})$ . Define two polynomials in $\mathbb{F}_{q}\left[z_{1},\dots,z_{|U|}\right]$ :

\text{TrueSum}\left(z_{1},\dots,z_{|U|}\right)=\sum_{i=1}^{|U|}z_{x_{i}},% \qquad\text{HistSum}\left(z_{1},\dots,z_{|U|}\right)=\sum_{i=1}^{|U|}z_{first(% x_{i})}.

If some pair $i<j$ satisfies $x_{i}\neq x_{j}$ but $g_{b(x_{i})}(x_{i})=g_{b(x_{j})}(x_{j})$ (i.e., two distinct elements in the same bucket share a fingerprint), the coefficients of $z_{j}$ differ in the two polynomials, hence $\text{TrueSum}\not\equiv\text{HistSum}$ (as polynomials); if all fingerprints are unique, the polynomials coincide. Let $\Delta\left(z_{1},\dots,z_{|U|}\right)\coloneqq\text{TrueSum}-\text{HistSum}$ .

Evaluate TrueSum and HistSum at the point $(h(x))_{x\in U}$ by maintaining two accumulators, accTrue and accHist, in $\mathbb{F}_{q}$ :

$\blacksquare$

To evaluate TrueSum, for every element $x_{i}$ we encounter, we add $h(x_{i})$ to accTrue ( $\text{mod }q$ ).
$\blacksquare$
To evaluate HistSum, for every element $x_{i}$ , check if the $fingerprint(x_{i})$ was observed before in the $b(x_{i})$ -th bucket. We can differentiate between “new” and “not new” fingerprints by keeping an additional bit next to the fingerprints in the histogram, which doesn’t change the asymptotic memory requirements of the histogram.
- –
  
  If $fingerprint(x_{i})$ is new in the bucket, add $h(x_{i})H_{b(x_{i})}[fingerprint(x_{i})]$ to accHist ( $\text{mod }q$ ).
- –
  
  If $fingerprint(x_{i})$ is not a new fingerprint, we ignore it.

At the end, set $res\coloneqq\texttt{accTrue}-\texttt{accHist}\in\mathbb{F}_{q}$ , and note that $res=\Delta\left(h(x_{1}),\dots,h(x_{|U|})\right)$ .

Output

Let $\{\delta_{i}\}_{i\in[|\mathcal{D}|]}$ be an enumeration of $\mathcal{D}$ . For each $i$ , check if $\delta_{i}\bigl(h(x_{1}),\dots,h(x_{|U|})\bigr)=res$ ; on the first match set $\delta=\delta_{i}$ (if no matches are found, abort).

For this $\delta$ , and for each $z_{x}$ with a positive coefficient $a_{x}$ , create a new histogram entry (or increment the existing entry) for $g_{b(x)}(x)$ in bucket $b(x)$ with counter $a_{x}$ ; for each $z_{x}$ with a negative coefficient $a_{x}$ , subtract $a_{x}$ from the histogram entry of $g_{b(x)}(x)$ in bucket $b(x)$ .

The following lemmas are used in the correctness proof.

Lemma 21.

Let $X\subseteq U$ such that $|X|\leq n$ . Let $b:U\rightarrow\left[\frac{n}{\log n}\right]$ be a hash function as described in the preliminaries. We call $b^{-1}(j)$ the $j$ -th bucket. With probability at least $1-\frac{1}{n^{2}}$ , every bucket contains at most $6\log n$ distinct elements from $X$ .

Proof.

Fix some bucket $j$ . The expected number of distinct elements $x\in X$ in this bucket is at most $\log n$ . For any $x_{i}\in X$ , let $Z_{i}$ be an indicator for $b(x_{i})=j$ . Let $Z\coloneqq\sum_{i=1}^{n}Z_{i}$ indicate the number of distinct stream elements in this bucket, and $\mu\coloneqq\mathbb{E}[Z]\leq\log n$ . Schmidt–Siegel’s limited-independence Chernoff bound [31] states that the multiplicative Chernoff bound can be applied on binary variables that are $k$ -wise independent for $k\geq\lceil\frac{\delta\mu}{1-\mu/n}\rceil$ . In our case, as $b$ is $6\log n$ -wise independent, the bound is applicable for $\delta=5$ (for large enough $n$ ), obtaining that the probability that the $j$ -th bucket has more than $6\log n$ distinct stream elements is bounded by $\exp\left(-\frac{5^{2}\log n}{7}\right)<\frac{1}{n^{3}}$ . A union bound over all buckets implies that the probability that all buckets contain at most $6\log n$ elements is at least $1-\frac{n}{\log n}\cdot\frac{1}{n^{3}}>1-\frac{1}{n^{2}}$ . $\hfill\blacktriangleleft$

Lemma 22.

Denote $k=\frac{n}{\log n}$ , and let $X_{1},\dots,X_{k}\subseteq U$ be sets that are pairwise disjoint, such that $\forall i\in[k],|X_{i}|\leq 6\log n$ . Let $g_{i}:U\rightarrow[2^{10\log\log n}]$ be hash functions as described in the preliminaries. For $x_{j}\in X_{i}$ we call $g_{i}(x_{j})$ the fingerprint of $x_{j}$ . We say a set $X_{i}$ contains a fingerprint collision if $\exists x_{k}\neq x_{m}\in X_{i}$ such that $g_{i}(x_{k})=g_{i}(x_{m})$ . Then, with probability at least $1-\frac{1}{n^{2}}$ , less than $\frac{n}{(\log n)^{6}}$ of the sets $X_{1},\dots,X_{k}$ contain a fingerprint collision.

Proof.

For every set $X_{i}$ let $Z_{i}$ be an indicator that there is a fingerprint collision in this set, and let $Z\coloneqq\sum_{i=1}^{k}Z_{i}$ . As $g_{i}$ is pairwise independent, $p:=\Pr[Z_{i}=1]\leq\frac{\binom{6\log n}{2}}{(\log n)^{10}}\leq\frac{18}{(\log n% )^{8}}$ , and by linearity of expectation, $\mu\coloneqq\mathbb{E}[Z]\leq\frac{18n}{(\log n)^{9}}$ . As the different $g_{i}$ hash functions are independent of one another, the $Z_{i}$ are independent random variables, therefore, by a Chernoff bound,

\Pr\left[Z\geq\frac{n}{(\log n)^{6}}\right]\leq\Pr\left[Z\geq(1+(\log n)^{2})% \mu\right]\leq\exp\left(-\frac{18n}{(\log n)^{3}}\right)<\frac{1}{n^{2}}.

Hence, with probability at least $1-\frac{1}{n^{2}}$ , less than $\frac{n}{(\log n)^{6}}$ sets have a fingerprint collision. $\hfill\blacktriangleleft$

Lemma 23.

$|\mathcal{D}|\leq 2^{n}$ (for all sufficiently large $n$ ).

Proof.

Let $s\coloneqq 6n/(\log n)^{5}$ . As throughout the paper, we assume $|U|\leq n^{c}$ for a constant $c>0$ . Then,

|\mathcal{D}|\leq\sum_{m=0}^{s}\binom{|U|}{m}(2n+1)^{m}\leq(s+1)\binom{|U|}{s}% (2n+1)^{s}\leq(s+1)\left(\frac{e|U|}{s}\right)^{s}(2n+1)^{s}.

Using $|U|\leq n^{c}$ and $s=6n/(\log n)^{5}$ ,

\log|\mathcal{D}|\leq\log(s{+}1)+s\Bigl(\log(e|U|/s)+\log(2n{+}1)\Bigr)=o(n).

Hence $\log|\mathcal{D}|\leq n$ for all sufficiently large $n$ , i.e., $|\mathcal{D}|\leq 2^{n}$ . $\hfill\blacktriangleleft$

Correctness

By Lemmas 21 and 22, with probability $>1-\frac{2}{n^{2}}$ , $\Delta$ has at most $s\coloneqq 6n/(\log n)^{5}$ non-zero coefficients, and all coefficients are integers in $[-n,n]$ , hence $\Delta\in\mathcal{D}$ . For any $\mathcal{D}\ni\delta\neq\Delta$ , by Schwartz-Zippel and the fact that they are both multi-linear,

\Pr_{h\in\mathbb{F}_{q}[z_{1},\dots,z_{|U|}]}\left[\delta(h(x_{1}),\dots,h(x_{% |U|}))=\Delta(h(x_{1}),\dots,h(x_{|U|}))\right]\leq\frac{1}{q}\leq\frac{1}{3^{% n}}.

Therefore, by a union bound over $\mathcal{D}$ , using Lemma 23,

\Pr_{h\in\mathbb{F}_{q}[z_{1},\dots,z_{|U|}]}\big[\exists\delta\in\mathcal{D}% \setminus\{\Delta\}:\delta(h)=\Delta(h)\big]\leq\frac{|\mathcal{D}|}{q}\leq% \left(\tfrac{2}{3}\right)^{n}.

Finally, if $\delta=\Delta$ , then $\text{TrueSum}\equiv\Delta+\text{HistSum}$ , hence all coefficients match and the correction step yields the exact histogram. Summing the failure probabilities from the two preliminary lemmas ( $\leq 2/n^{2}$ ) and the probability that some $\delta\neq\Delta$ coincides with $\Delta$ at $h$ gives an overall bound of $<3/n^{2}$ .

Representing the hash $𝒉$

Representing a fully random $h:U\to\mathbb{F}_{q}$ naively requires too much memory. Instead, we use Newman’s public–to–private randomness reduction [29], observing that it also works for streaming algorithms. For any problem with at most $N$ possible inputs, there exists a set of $O(\log N)$ values of the shared randomness such that picking uniformly from this set preserves the success probability up to a small additive error, simultaneously for all inputs. In particular, it suffices to only maintain in memory an index of one choice within this family, which requires only $O(\log\log N)$ bits of space. In our case, $N=|U|^{n}$ bounds the number of possible streams.

Memory cost

Hash functions.

The function $b$ is $6\log n$ -wise independent, requiring $O(\log^{2}n)$ bits of memory. The functions $g_{j}$ are $\frac{n}{\log n}$ pairwise independent hash functions, each requiring $O(\log n)$ bits to describe, for a total of $O(n)$ bits.

Counters in histograms.

The total sum of all counters is $n$ , hence all counters together require at most $O(n)$ bits.

Fingerprints.

Each bucket stores at most $6\log n$ distinct fingerprints with high probability (by Lemma 21). Each fingerprint uses $10\log\log n$ bits. Since there are $\frac{n}{\log n}$ buckets, the total fingerprint storage is

\frac{n}{\log n}\cdot 6\log n\cdot 10\log\log n=O(n\log\log n).

Second pass.

We store two accumulators in $\mathbb{F}_{q}$ , requiring $\Theta(n)$ bits total, and reuse $O(n)$ working memory while enumerating candidates $\delta\in\mathcal{D}$ .

Summing all contributions gives

O(n)+O(n)+O(n\log\log n)+O(n)=O(n\log\log n).

6.2 Higher Number of Passes and Further Remarks

We remark that an algorithm using only $O(n)$ memory cannot compute $F_{2}$ exactly with probability $>2/3$ , let alone the full histogram, with any constant number of passes over the stream. This follows from the $r$ -rounds communication lower bound of $\Omega\left(n\log^{(r)}n\right)$ for the set disjointness problem, established by Sağlam and Tardos [30]. For any constant $r$ , by the standard streaming–communication simulation, their result implies a corresponding $\Omega\left(n\log^{(2r-1)}n\right)$ lower bound for $r$ -pass streaming algorithms. We note that for super-constant $r$ , there also exists an algorithm that calculates exact histograms with only $\tilde{O}(n/r+\sqrt{n})$ bits of memory, by using each pass to compute an exact histogram of another $1/r$ fraction of the element identities and finally aggregating it with a succinctly represented histogram of the elements processed in the rounds so far. This is near optimal, as a lower bound of $\Omega(n/r)$ can be obtained from the two-way communication bound of $\Omega(n)$ for set-disjointness, and a $\Omega(\sqrt{n})$ lower bound follows from the memory required to represent a histogram.

On the positive side, the set-intersection communication protocol of Brody et al. [11], on which our streaming algorithm is based, extends naturally to $r$ rounds and yields an $O\left(n\log^{\left(\Omega(r)\right)}n\right)$ upper bound in the communication model. Using the ideas we introduced, the full version of this paper translates their protocol into the streaming setting and extends them to obtain an analogous $r$ -pass streaming upper bound. Specifically, the full version proves using $(2r-1)$ -passes, $O\left(n\log^{(r)}n\right)$ bits of memory suffice for exactly computing the histogram.

Finally, while our three-pass algorithm is also efficient in terms of running time, our two-pass algorithm is not. Since our focus is on space complexity, we presented the simplest solution we could find; however, it is likely that efficiency can be achieved using standard polynomial sparse-recovery techniques [37, 6, 22].

7 Summary and Open Problems

We provide tight bounds for estimating the second frequency moment $F_{2}$ of a data stream in the low-error regime $\varepsilon<1/\sqrt{n}$ . Our results fully characterize the one-pass space complexity of $(1\pm\varepsilon)$ -approximating $F_{2}$ for all values of $\varepsilon$ , matching upper and lower bounds up to constant factors. Central to our approach is a precise understanding of the communication complexity of Approximate Set Intersection, which exhibits a sharp phase transition at $\varepsilon=1/\sqrt{n}$ .

We also present a two-pass streaming algorithm that exactly computes a histogram using $O(n\log\log n)$ bits of memory, showing a strict asymptotic separation between one-pass and constant-pass space complexity for $F_{2}$ estimation when $\varepsilon<1/\sqrt{n}$ . This naturally leads to the following question. Is there also a separation between one-pass and $O(1)$ -pass streaming algorithms for $F_{2}$ estimation in the regime $\varepsilon>1/\sqrt{n}$ ? The older $\Omega(1/\varepsilon^{2}+\log n)$ space lower bound for $F_{2}$ is now known to be sub-optimal for one-pass yet holds also for any constant number of passes. Can either the lower bound or algorithm be improved in these settings?

We also leave as an open problem characterizing the exact trade-off between the number of passes and memory required for exactly computing a stream’s histogram. For example, using two passes we currently have a gap between our $O(n\log\log n)$ upper bound and the $\Omega(n\log\log\log n)$ lower bound implied by the communication complexity of Set Intersection.

References

[1] Noga Alon, Phillip B Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. In Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 10–20, 1999. doi:10.1145/303976.303978.
[2] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20–29, 1996. doi:10.1145/237814.237823.
[3] Alexandr Andoni. High frequency moments via max-stability. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6364–6368. IEEE, 2017. doi:10.1109/ICASSP.2017.7953381.
[4] Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 363–372. IEEE, 2011. doi:10.1109/FOCS.2011.82.
[5] Ziv Bar-Yossef, Thathachar 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, 2004. doi:10.1016/J.JCSS.2003.11.006.
[6] Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 301–309, 1988.
[7] Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. Simpler algorithm for estimating frequency moments of data streams. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 708–713, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109634.
[8] Mark Braverman and Or Zamir. Optimality of frequency moment estimation. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), Prague, Czech Republic, June 2025.
[9] Vladimir Braverman and Rafail Ostrovsky. Recursive sketching for frequency moments. arXiv preprint, 2010. arXiv:1011.2571.
[10] Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. Revisiting Frequency Moment Estimation in Random Order Streams. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.25.
[11] Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, pages 106–113, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2611462.2611501.
[12] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 107–117. IEEE, 2003. doi:10.1109/CCC.2003.1214414.
[13] Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance, 2012. arXiv:1009.3460.
[14] Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 517–528, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. doi:10.1007/978-3-642-32512-0_44.
[15] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.
[16] Sumit Ganguly. A lower bound for estimating high moments of a data stream. arXiv preprint, 2011. arXiv:1201.0253.
[17] Sumit Ganguly. Polynomial estimators for high frequency moments. arXiv preprint, 2011. arXiv:1104.4552.
[18] Anna C Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, Sivaramakrishnan Muthukrishnan, and Martin J Strauss. Fast, small-space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 389–398, 2002.
[19] T. E. Harris. A lower bound for the critical probability in a certain percolation process. Mathematical Proceedings of the Cambridge Philosophical Society, 56(1):13–20, 1960. doi:10.1017/S0305004100034241.
[20] Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 202–208, 2005. doi:10.1145/1060590.1060621.
[21] Rajesh Jayaram and David P. Woodruff. Towards Optimal Moment Estimation in Streaming and Distributed Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.29.
[22] Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In International Symposium on Symbolic and Algebraic Computation, pages 467–474. Springer, 1988. doi:10.1007/3-540-51084-2_44.
[23] 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, pages 1161–1178. SIAM, 2010. doi:10.1137/1.9781611973075.93.
[24] Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pages 234–247, 2003. doi:10.1145/948205.948236.
[25] Yi Li and David P Woodruff. A tight lower bound for high frequency moment estimation with small error. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 623–638. Springer, 2013. doi:10.1007/978-3-642-40328-6_43.
[26] Jeřábek Meir. Communication complexity of approximating the size of set intersection, June 2018. Theoretical Computer Science, Stack Exchange. URL: https://cstheory.stackexchange.com/questions/41086/communication-complexity-of-approximating-the-size-of-set-intersection.
[27] Morteza Monemizadeh and David P Woodruff. 1-pass relative-error lp-sampling with applications. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1143–1160. SIAM, 2010. doi:10.1137/1.9781611973075.92.
[28] Jelani Nelson and Huacheng Yu. Optimal bounds for approximate counting. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 119–127, 2022. doi:10.1145/3517804.3526225.
[29] Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67–71, 1991. doi:10.1016/0020-0190(91)90157-D.
[30] Mert Saglam and Gabor Tardos. On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 678–687, Los Alamitos, CA, USA, October 2013. IEEE Computer Society. doi:10.1109/FOCS.2013.78.
[31] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff–hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223–250, 1995. doi:10.1137/S089548019223872X.
[32] Irina G. Shevtsova. On the absolute constant in the berry–esseen inequality. Doklady Mathematics, 82(3):862–864, 2010. doi:10.1134/S1064562410030099.
[33] David P Woodruff. Optimal space lower bounds for all frequency moments. In SODA, volume 4, pages 167–175. Citeseer, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982817.
[34] David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 941–960, 2012. doi:10.1145/2213977.2214063.
[35] David P Woodruff and Samson Zhou. Separations for estimating large frequency moments on data streams. In ICALP, 2021.
[36] Andrew C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 222–227. IEEE, 1977.
[37] Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation, pages 216–226. Springer, 1979. doi:10.1007/3-540-09519-5_73.

[bib.bib1] [1] Noga Alon, Phillip B Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. In Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 10–20, 1999. doi:10.1145/303976.303978.

[bib.bib2] [2] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20–29, 1996. doi:10.1145/237814.237823.

[bib.bib3] [3] Alexandr Andoni. High frequency moments via max-stability. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6364–6368. IEEE, 2017. doi:10.1109/ICASSP.2017.7953381.

[bib.bib4] [4] Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 363–372. IEEE, 2011. doi:10.1109/FOCS.2011.82.

[bib.bib5] [5] Ziv Bar-Yossef, Thathachar 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, 2004. doi:10.1016/J.JCSS.2003.11.006.

[bib.bib6] [6] Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 301–309, 1988.

[bib.bib7] [7] Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha. Simpler algorithm for estimating frequency moments of data streams. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 708–713, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109634.

[bib.bib8] [8] Mark Braverman and Or Zamir. Optimality of frequency moment estimation. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), Prague, Czech Republic, June 2025.

[bib.bib9] [9] Vladimir Braverman and Rafail Ostrovsky. Recursive sketching for frequency moments. arXiv preprint, 2010. arXiv:1011.2571.

[bib.bib10] [10] Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. Revisiting Frequency Moment Estimation in Random Order Streams. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.25.

[bib.bib11] [11] Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, pages 106–113, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2611462.2611501.

[bib.bib12] [12] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 107–117. IEEE, 2003. doi:10.1109/CCC.2003.1214414.

[bib.bib13] [13] Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance, 2012. arXiv:1009.3460.

[bib.bib14] [14] Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 517–528, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. doi:10.1007/978-3-642-32512-0_44.

[bib.bib15] [15] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.

[bib.bib16] [16] Sumit Ganguly. A lower bound for estimating high moments of a data stream. arXiv preprint, 2011. arXiv:1201.0253.

[bib.bib17] [17] Sumit Ganguly. Polynomial estimators for high frequency moments. arXiv preprint, 2011. arXiv:1104.4552.

[bib.bib18] [18] Anna C Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, Sivaramakrishnan Muthukrishnan, and Martin J Strauss. Fast, small-space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 389–398, 2002.

[bib.bib19] [19] T. E. Harris. A lower bound for the critical probability in a certain percolation process. Mathematical Proceedings of the Cambridge Philosophical Society, 56(1):13–20, 1960. doi:10.1017/S0305004100034241.

[bib.bib20] [20] Piotr Indyk and David Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 202–208, 2005. doi:10.1145/1060590.1060621.

[bib.bib21] [21] Rajesh Jayaram and David P. Woodruff. Towards Optimal Moment Estimation in Streaming and Distributed Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.29.

[bib.bib22] [22] Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In International Symposium on Symbolic and Algebraic Computation, pages 467–474. Springer, 1988. doi:10.1007/3-540-51084-2_44.

[bib.bib23] [23] 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, pages 1161–1178. SIAM, 2010. doi:10.1137/1.9781611973075.93.

[bib.bib24] [24] Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pages 234–247, 2003. doi:10.1145/948205.948236.

[bib.bib25] [25] Yi Li and David P Woodruff. A tight lower bound for high frequency moment estimation with small error. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 623–638. Springer, 2013. doi:10.1007/978-3-642-40328-6_43.

[bib.bib26] [26] Jeřábek Meir. Communication complexity of approximating the size of set intersection, June 2018. Theoretical Computer Science, Stack Exchange. URL: https://cstheory.stackexchange.com/questions/41086/communication-complexity-of-approximating-the-size-of-set-intersection.

[bib.bib27] [27] Morteza Monemizadeh and David P Woodruff. 1-pass relative-error lp-sampling with applications. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1143–1160. SIAM, 2010. doi:10.1137/1.9781611973075.92.

[bib.bib28] [28] Jelani Nelson and Huacheng Yu. Optimal bounds for approximate counting. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 119–127, 2022. doi:10.1145/3517804.3526225.

[bib.bib29] [29] Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67–71, 1991. doi:10.1016/0020-0190(91)90157-D.

[bib.bib30] [30] Mert Saglam and Gabor Tardos. On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems . In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 678–687, Los Alamitos, CA, USA, October 2013. IEEE Computer Society. doi:10.1109/FOCS.2013.78.

[bib.bib31] [31] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff–hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223–250, 1995. doi:10.1137/S089548019223872X.

[bib.bib32] [32] Irina G. Shevtsova. On the absolute constant in the berry–esseen inequality. Doklady Mathematics, 82(3):862–864, 2010. doi:10.1134/S1064562410030099.

[bib.bib33] [33] David P Woodruff. Optimal space lower bounds for all frequency moments. In SODA, volume 4, pages 167–175. Citeseer, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982817.

[bib.bib34] [34] David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 941–960, 2012. doi:10.1145/2213977.2214063.

[bib.bib35] [35] David P Woodruff and Samson Zhou. Separations for estimating large frequency moments on data streams. In ICALP, 2021.

[bib.bib36] [36] Andrew C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), pages 222–227. IEEE, 1977.

[bib.bib37] [37] Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation, pages 216–226. Springer, 1979. doi:10.1007/3-540-09519-5_73.

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

Theorem 3.

2 Overview and Organization

Section 3: Communication lower bounds and streaming implications, in the 𝜺<𝟏/𝒏 range

Section 4: Matching upper bounds via hashing

Section 5: The high-error regime

Section 6: A two-pass algorithm for exact histograms

Section 7: Summary

3 Lower Bounds in the Low Error Regime

3.1 Approximate Set Intersection

Definition 4 (INTε).

Definition 5 (INT-Pα Promise Problem).

Definition 6 (Design).

Definition 7 (Block-Uniform Distribution 𝒟n,α).

Lemma 8.

Proof.

Lemma 9 (Random Y distinguishes between X and X′).

Proof.

Step 1: Chernoff bound for 𝒁same.

Step 2: Berry–Esseen tail bound for 𝒁𝐝𝐢𝐟𝐟 and 𝒁𝐝𝐢𝐟𝐟′.

Step 3: Combining bounds.

Step 4: Negative correlation between 𝒁𝒅⁢𝒊⁢𝒇⁢𝒇 and 𝒁𝒅⁢𝒊⁢𝒇⁢𝒇′.

Step 5: Symmetry.

Lemma 10 (Existence of family 𝒴 fully distinguishing a design 𝒳).

Proof.

Lemma 11.

Proof.

3.2 Second Moment Estimation

Corollary 12.

Proof.

4 Upper Bounds in the Low Error Regime

4.1 Second Moment Estimation

Lemma 13.

Algorithm 𝓐

Claim 14.

Proof.

Claim 15.

Proof.

4.2 Approximate Set Intersection

Corollary 16.

Proof.

5 Approximate Set Intersection in the High Error Regime

5.1 Lower Bound

Lemma 17.

Proof.

5.2 Upper Bound

Lemma 18.

Proof.

Algorithm 1 (One-way, 𝑶⁢((𝐥𝐨𝐠⁡𝒏)/𝜺𝟐) bits).

Algorithm 2 (Two-way, 𝑶⁢(𝟏/𝜺𝟐) bits).

Algorithm 3 (One-way, 𝑶⁢(𝟏/𝜺𝟐) bits).

Private randomness.

6 Multipass Histogram Streaming

6.1 Two–Pass Algorithm

Lemma 19.

Preliminaries

Definition 20.

The algorithm

Pass 1 (fingerprint histograms)

Pass 2 (sparse recovery)

Output

Lemma 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Section 3: Communication lower bounds and streaming implications, in the $\varepsilon<1/\sqrt{n}$ range

Definition 4 ( $\mathrm{INT}^{\varepsilon}$ ).

Definition 5 ( $\text{INT-P}^{\alpha}$ Promise Problem).

Definition 7 (Block-Uniform Distribution $\mathcal{D}_{n,\alpha}$ ).

Lemma 9 (Random $Y$ distinguishes between $X$ and $X^{\prime}$ ).

Step 1: Chernoff bound for $Z_{\text{same}}$ .

Step 2: Berry–Esseen tail bound for $Z_{\mathrm{diff}}$ and $Z^{\prime}_{\mathrm{diff}}$ .

Step 4: Negative correlation between $Z_{diff}$ and $Z^{\prime}_{diff}$ .

Lemma 10 (Existence of family $\mathcal{Y}$ fully distinguishing a design $\mathcal{X}$ ).

Algorithm $\mathcal{A}$

Algorithm 1 (One-way, $O((\log n)/\varepsilon^{2})$ bits).

Algorithm 2 (Two-way, $O(1/\varepsilon^{2})$ bits).

Algorithm 3 (One-way, $O(1/\varepsilon^{2})$ bits).

Representing the hash $𝒉$