Abstract
We study distribution testing with communication and memory constraints inthe following computational models: (1) The {\em onepass streaming model}where the goal is to minimize the sample complexity of the protocol subject toa memory constraint, and (2) A {\em distributed model} where the data samplesreside at multiple machines and the goal is to minimize the communication costof the protocol. In both these models, we provide efficient algorithms foruniformity/identity testing (goodness of fit) and closeness testing (two sampletesting). Moreover, we show nearlytight lower bounds on (1) the samplecomplexity of any onepass streaming tester for uniformity, subject to thememory constraint, and (2) the communication cost of any uniformity testingprotocol, in a restricted `onepass' model of communication.
Quick Read (beta)
[
Abstract
We study distribution testing with communication and memory constraints in the following computational models: (1) The onepass streaming model where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A distributed model where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearlytight lower bounds on (1) the sample complexity of any onepass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted “onepass” model of communication.
Communication and Memory Efficient Testing of Discrete Distributions]Communication and Memory Efficient Testing
of Discrete Distributions
istribution testing, identity testing, closeness testing, communication complexity, streaming
1 Introduction
1.1 Background
Classical statistics theory focuses on characterizing the inherent sample complexity of inference tasks, typically formalized via minimax rates of convergence. Research in this field has primarily focused on understanding the sample complexity of inference in the centralized setting, where all the samples are available to a single machine that performs the computation. We now have a rich theory (see, e.g., [Devroye and Györfi(1985), Devroye and Lugosi(2001), Tsybakov(2008)] for a few books on the topic) that has led to characterizing the sample complexity of a wide range of statistical tasks in this regime.
In modern data analysis, one may have additional constraints on data collection and storage. Modern datasets are often too large to be stored on a single computer, and so it is natural to consider methods that either impose upper bounds on the available memory or involve multiple machines, each containing a small subset of the dataset. Typical examples include anomaly detection in various settings (e.g., inference based on distributed sensor measurements, fraud detection based on different transactions of a customer, deciding whether a region of the sky is interesting based on astronomical data from multiple telescopes, etc.)
In this paper, we study distribution property testing [Batu et al.(2000)Batu, Fortnow, Rubinfeld, Smith, and White] in the following computational models: (1) The onepass streaming model where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A distributed model where the data samples reside at multiple machines, and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show lower bounds (in some cases, nearlytight) on (1) the sample complexity of any onepass streaming tester, subject to the memory constraint and (2) the communication cost of any protocol performing the testing task (in a restricted “onepass” model of communication, described below).
Computational Models
In the onepass streaming model, the data samples are revealed online in a stream and the algorithm is allowed a single pass over the data. Moreover, there is an upper bound, which we will typically denote by $m$, on the number of bits the algorithm can store at any point of its execution. In our setting, the goal is to minimize the sample complexity of testing subject to the memory constraint.
Our distributed communication model uses a blackboard (broadcast) model of communication in the sense that each message sent by each machine (player) is visible to all machines. There is an arbitrarily large number of machines, each holding $\mathrm{\ell}$ independent samples from the unknown distribution(s). Additionally, there is a referee (arbitrator) who holds no samples. In each round, the referee either returns an answer or asks a onebit question to one of the players about their input and receives a response. The goal is for the referee to return the correct answer to our testing problem (with at least $2/3$ probability) in as few rounds of communication as possible. Notice that this model only costs the communication needed to answer the referee’s questions and not the information encoded by the questions themselves or by which player the referee chooses to ask. This is natural in a broadcast communication model, as this information would be implicitly determined by the communication transcript up to this point.
Unfortunately, we do not know how to prove lower bounds in the above general model, and will instead work in the onepass version of this model. In the onepass version, the referee is not allowed to go back to querying a player after they have moved on. In particular, the referee cannot ask a question to player $A$, subsequently ask a question to player $B\ne A$, and then ask a question to player $A$ again. Our communication lower bounds hold in this onepass model. We note that our algorithms work in the onepass model as well.
1.2 Our Contributions
We give algorithms and lower bounds for uniformity/identity testing^{1}^{1} 1 The reduction of identity to uniformity in [Goldreich(2016)] immediately translates our upper bounds from uniformity to identity. and closeness testing in the presence of communication and memory constraints. More specifically, we obtain the following results:

1.
A onepass streaming algorithm for uniformity testing on $[n]$ with memory upper bound of $m$ bits that has sample complexity $O(n\mathrm{log}(n)/(m{\u03f5}^{4}))$ for a broad range of parameters. Moreover, we show that this sample upper bound is tight for a fairly wide range of $m$, and tight up to a $\mathrm{log}(n)$ factor when $\u03f5$ is constant for all values of $m$.

2.
A distributed uniformity tester for $\mathrm{\ell}$ samples per machine with communication complexity $O(\sqrt{n\mathrm{log}(n)/\mathrm{\ell}}/{\u03f5}^{2})$. (Note that when $\mathrm{\ell}=1$, this beats the trivial algorithm by a $\sqrt{\mathrm{log}(n)}$ factor.) We also give a matching lower bound when $\mathrm{\ell}$ is not too big and $\u03f5$ is not too small. The former of these constraints on the lower bound is necessary. Indeed, we give a different algorithm with communication $O(n\mathrm{log}(n)/({\mathrm{\ell}}^{2}{\u03f5}^{4}))$, which beats the previous bound when $\mathrm{\ell}$ is sufficiently large.

3.
A onepass streaming algorithm for closeness testing that uses $O(n\sqrt{\mathrm{log}(n)/m}/{\u03f5}^{2})$ samples for a wide range of values of $m$, and a distributed closeness tester with communication complexity $O({n}^{2/3}{\mathrm{log}}^{1/3}(n)/({\mathrm{\ell}}^{2/3}{\u03f5}^{4/3}))$. (Note that for $\mathrm{\ell}=1$, this improves by a ${\mathrm{log}}^{2/3}(n)$ factor over the naive algorithm.)
Our results are summarized in Tables 1 and 2.
Sample Complexity Bounds with Memory Constraints  
Property  Upper Bound  Lower Bound 1  Lower Bound 2 
Uniformity  $O\left(\frac{n\mathrm{log}n}{m{\u03f5}^{4}}\right)$  $\mathrm{\Omega}\left(\frac{n\mathrm{log}n}{m{\u03f5}^{4}}\right)$  $\mathrm{\Omega}\left(\frac{n}{m{\u03f5}^{2}}\right)$ 
Conditions  ${n}^{0.9}\gg m\gg \mathrm{log}\left(n\right)/{\u03f5}^{2}$  $m=\stackrel{~}{\mathrm{\Omega}}\left(\frac{{n}^{0.34}}{{\u03f5}^{8/3}}+\frac{{n}^{0.1}}{{\u03f5}^{4}}\right)$  Unconditional 
Closeness  $O\left(n\sqrt{\mathrm{log}\left(n\right)}/\left(\sqrt{m}{\u03f5}^{2}\right)\right)$  –  – 
Conditions  $\stackrel{~}{\mathrm{\Theta}}\left(\mathrm{min}(n,{n}^{2/3}/{\u03f5}^{4/3})\right)\gg m\gg \mathrm{log}\left(n\right)$  –  – 
Communication Complexity Bounds  
Property  UB 1  UB 2  LB 1  LB 2  LB 3 
Uniformity  $O\left(\frac{\sqrt{n\mathrm{log}\left(n\right)/\mathrm{\ell}}}{{\u03f5}^{2}}\right)$  $O\left(\frac{n\mathrm{log}\left(n\right)}{{\mathrm{\ell}}^{2}{\u03f5}^{4}}\right)$  $\mathrm{\Omega}\left(\frac{\sqrt{n\mathrm{log}\left(n\right)/\mathrm{\ell}}}{{\u03f5}^{2}}\right)$  $\mathrm{\Omega}\left(\frac{\sqrt{n/\mathrm{\ell}}}{\u03f5}\right)$  $\mathrm{\Omega}\left(\frac{n}{{\mathrm{\ell}}^{2}{\u03f5}^{2}\mathrm{log}n}\right)$ 
Conditions  $\frac{{\u03f5}^{8}n}{\mathrm{log}n}\gg \mathrm{\ell}\gg \frac{{\u03f5}^{4}}{{n}^{0.9}}$  $\mathrm{\ell}\ll \frac{\sqrt{n}}{{\u03f5}^{2}}$  ${\u03f5}^{4/3}{n}^{0.3}\gg \mathrm{\ell}$  $\mathrm{\ell}=\stackrel{~}{O}\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}}\right)$  $\mathrm{\ell}=\stackrel{~}{\mathrm{\Omega}}\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}}\right)$ 
Closeness  $O\left(\frac{{n}^{2/3}{\mathrm{log}}^{1/3}\left(n\right)}{{\mathrm{\ell}}^{2/3}{\u03f5}^{4/3}}\right)$         
Conditions  $n{\u03f5}^{4}/\mathrm{log}\left(n\right)\gg \mathrm{\ell}$         
1.3 Overview of our Approach
In this section, we provide a detailed sketch of our algorithms and lower bounds.
Uniformity Testing Algorithms
We start by describing the main ideas underlying our efficient uniformity testing protocols. We note that in both the distributed and the streaming settings, our uniformity testers rely on a unified idea that we term bipartite collision testing. We remind the reader that testing uniformity based on the number of pairwise collisions is the oldest algorithm in distribution testing [Goldreich and Ron(2000)], which is now known to be sampleoptimal in the centralized setting [Diakonikolas et al.(2016)Diakonikolas, Gouleakis, Peebles, and Price]. (In fact, it turns out that all known efficient uniformity testers rely to some extent on counting pairwise collisions.) Recall that the collisionsbased uniformity tester [Goldreich and Ron(2000)] takes $N$ samples from the unknown distribution $p$ on $[n]$ and counts the total number of pairwise collisions among them. If $p$ is the uniform distribution, the expected number of collisions will be $(1/n)\cdot \left(\genfrac{}{}{0pt}{}{N}{2}\right)$. On the other hand, if $p$ is $\u03f5$far from the uniform distribution, the expected number of collisions will be at least $(1/n)\cdot \left(\genfrac{}{}{0pt}{}{N}{2}\right)(1+\mathrm{\Theta}({\u03f5}^{2}))$. A now standard analysis — involving carefully bounding the variance of this estimator followed by an application of Chebyshev’s inequality — shows that for $N=\mathrm{\Omega}(\sqrt{n}/{\u03f5}^{2})$ we can distinguish between the two cases with high constant probability.
Unfortunately, the standard collisionsbased tester described above involves computing the total number of collisions among all pairs of samples, and it is unclear if it can be implemented with nontrivial communication or memory. ^{2}^{2} 2 We note that the trivial protocol based on a total of $N$ samples uses $N\cdot \mathrm{log}n$ bits of memory and $N\cdot \mathrm{log}n$ bits of communication. To improve on these naive bounds, we propose a modified uniformity tester (in the collocated/centralized setting) that we can implement in the memory and communication restricted settings we study. In particular, we consider a bipartite collision tester that works as follows: We draw two independent sets of samples ${S}_{1}$ and ${S}_{2}$ from the unknown distribution $p$ and count the number of pairs of an element of ${S}_{1}$ and an element of ${S}_{2}$ that collide. Importantly, we will use this scheme in such a way so that the first set of samples ${S}_{1}$ will be substantially smaller than the second set of samples ${S}_{2}$. Roughly speaking, our algorithm will store the set ${S}_{1}$ exactly, while for each element of the set ${S}_{2}$, it will only need to know the number of collisions with elements of ${S}_{1}$. This last step will allow us to save on space or communication. An important technical condition that is required for our bipartite tester to succeed is that ${S}_{1}\cdot {S}_{2}\gg n/{\u03f5}^{4}$.
We now provide an overview of the analysis. As is standard, we need to show that the number of collisions is much larger in the nonuniform case than in the uniform case. To achieve that, we consider for fixed ${S}_{1}$ the sum $p({S}_{1})={\sum}_{s\in {S}_{1}}{p}_{s}$. We note that the expected number of collisions is just $p({S}_{1})\cdot {S}_{2}$, and by standard concentration bounds one can show that it will likely be close to this value. However, the average size of $p({S}_{1})$ is ${S}_{1}\cdot {\parallel p\parallel}_{2}^{2}$, which is somewhat larger for nonuniform $p$ than for $p$ uniform. The detailed analysis is given in Section 3.1.
We note that our bipartite collision tester can be easily implemented in the memory and communication bounded settings. In the former setting (Section 3.2), it leads to a uniformity tester with sample complexity $O(n\mathrm{log}n/(m{\u03f5}^{4}))$, where $m$ is the bits of memory used. In the distributed setting (Section 3.3), when each machine stores $\mathrm{\ell}$ samples, it leads to a tester with sample complexity $O(\sqrt{n\mathrm{\ell}\mathrm{log}n}/{\u03f5}^{2})$ and communication cost $O(\sqrt{(n\mathrm{log}n)/\mathrm{\ell}}/{\u03f5}^{2})$ bits. (It should be noted that the above memory and communication upper bounds match our lower bounds in some regimes of parameters. We show that the tradeoff between sample complexity and memory/communication is inherent. See Theorem 4.2 and Corollary 4.3.)
It should be noted that when $\mathrm{\ell}$ is sufficiently large, we can design a uniformity tester whose communication beats the above (Section 3.4). This fact should not be surprising since if $\mathrm{\ell}\gg \sqrt{n}/{\u03f5}^{2}$, a single machine could run a uniformity tester and simply return the answer. If $\mathrm{\ell}$ is somewhat smaller than this value, we can still take advantage of the large number of samples per machine. The basic idea is for each player to communicate the number of pairwise collisions among their own samples. As there are $O({\mathrm{\ell}}^{2})$ pairs of samples per machine, this will require roughly $n/{\mathrm{\ell}}^{2}$ machines before we start seeing any collisions, and this will give our approximate complexity for large $\u03f5$, which can be seen to be better than our aforementioned bound, when $\mathrm{\ell}$ is sufficiently large.
InformationTheoretic Lower Bounds.
We start by describing our memory lower bounds followed by our communication lower bounds.
Memory Lower Bound. We define a family of distributions on $[n]\times [2]$, i.e., supported on $2n$ elements that will make uniformity testing difficult. In particular, we think of these distributions as consisting of $n$ pairs of bins where the probability of landing in each pair is exactly $1/n$. Equivalently, a distribution from this family can be thought of as having $n$ (possibly biased) coins. The distribution picks a uniform random coin, flips it, and returns the pair of the coin and the result. If all coins are fair, we have the uniform distribution over $[n]\times [2]$. On the other hand, if each coin is $\u03f5$biased in a randomly chosen direction, we have a distribution that is $\u03f5$far from uniform. We show that these two cases are hard to distinguish from each other without expending a substantial amount of our computational resources. Note that the standard sample complexity lower bounds for uniformity testing [Paninski(2008)] rely on essentially the same hard instances.
We consider running a testing algorithm on a distribution that is randomly either uniform or a random $\u03f5$biased distribution as described above. Let $X$ be the bit that describes whether or not the distribution is uniform or not. We consider the shared information between $X$ and the memory of our algorithm after seeing $k$ samples. We will attempt to show that this increases by at most $O({\u03f5}^{2}m/n)$ per step, where $m$ is the upper bound on the memory, which implies that it will take $\gg n/(m{\u03f5}^{2})$ steps in order to reliably determine $X$. The idea of the proof is fairly simple: The choice of which of the $n$ coins is flipped is uniform no matter what, and so this choice does not tell us anything about $X$. What might tell us something is the result of flipping this coin, but two things make this difficult for us. On the one hand, the coin is at most $\u03f5$biased, so knowing the result of the flip can only provide $O({\u03f5}^{2})$ information about this bias. More critically, a biased coin is equally likely to be biased in either direction, so knowing the result by itself still tells us nothing unless we have some prior information about the direction of the possible bias. However, since our streaming algorithm can store only $m$ bits of memory, on average it has at most $O(m/n)$ bits of information about the bias of the (randomly chosen) coin of the next flip. This argument can be formalized to show that the next flip can only contribute $O(m/n)$ bits to the shared information between $X$ and our memory. See Section 4.2.
It may seem that the above argument is tight. With $m$ bits of information, one could know the biases (if they exist) of $m$ of the coins, and then each flip will (with probability $m/n$) give us ${\u03f5}^{2}$ information to accept or reject our hypothesis that these biases are real. However, we would need to be extraordinarily lucky to have this information. The only way that we could know the biases of these $m$ coins is if in our previous set of samples we had seen each of these coins $m$ times. This will prove difficult for two reasons: First, unless the number of samples is quite large, we would not expect to see any coin show up in more than, say, $10$ samples. This will limit the amount of information we could expect to know about the bias of any given coin to $O({\u03f5}^{2})$. Additionally, we will have information about the biases of all of these particular $m$ coins only if all of them have shown up in our set of samples. But if our total number of samples is substantially sublinear, this will only happen with probability ${n}^{\mathrm{\Omega}(m)}$. On the other hand, since there are only ${2}^{m}$ possible memory states, with high probability, we must be in one that occurs with probability only as small as ${2}^{\mathrm{\Omega}(m)}$, so we should only hope to have this information about $m/\mathrm{log}(n)$ coins (which we could get by, say, recording the coins and the results of the first $m/\mathrm{log}(n)$ samples). To formalize this intuition, we let $r$ be the vector whose ${i}^{th}$ entry is the expected number of times we have seen the ${i}^{th}$ coin based on the transcript, and note that the information gained is proportional to ${\parallel r\parallel}_{2}^{2}$. This can only be large if there is some unit vector $w$ with $w\cdot r$ large. But this would in turn mean that, conditioned on our (reasonably high probability) transcript, the average of ${w}_{C}$ over our samples $C$ is big. We show that this cannot happen with high probability by a Chernoff bound. The details are deferred to Section 4.2.
Communication Complexity Lower Bound. To make this argument work for our communication complexity setting (Section 4.3), we will need to restrict the model, in particular requiring that the referee sees the players in sequence, never returning to one after it has moved onto the next. In order to get our lower bounds for many samples per player, we can proceed by immediate reduction to the streaming model. Our algorithm stores the transcript of the communication thus far. When the referee talks to a new player, we record the samples that this player has, and then we compress this down to the extended transcript involving the answers to the questions asked of this new player. Note that at any time the amount of memory used is at most $O(T+s\mathrm{log}(n))$, where $T$ is the final communication transcript.
Closeness Testing Algorithms
We now describe our algorithms for closeness testing (Section 5). In the communication model, a reasonable approach would be to follow the methodology of [Diakonikolas and Kane(2016)], by first using a few samples to flatten and then applying some collisionbased tester similar to that used for our uniformity testers. We instead give an algorithm that turns out to be slightly more communication efficient. The essential idea is to pick a random subset $W$ of the domain, and test whether or not $p$ conditioned on $W$ is close to $q$ conditioned on $W$. If we take $W$ to be about $n/(s\mathrm{log}(n))$, we note that each machine can send either one bit (encoding that they have no samples in $W$) or $\mathrm{log}(n)$ bits giving one such sample. The former outcome happens about $\mathrm{log}(n)$ times more often, and so in total we need to send about $\mathrm{log}(n)$ bits per element of $S$ received. However, for constant $\u03f5$, we should need only about ${W}^{2/3}$ such samples to run a standard closeness tester.
There is one substantial issue with this plan however. We need it to be the case that $\mathrm{\mathbf{P}\mathbf{r}}[W]$ is approximately $W/n$ and that ${d}_{\mathrm{T}V}(pW,qW)\approx {d}_{\mathrm{T}V}(p,q)$. We note that both of these happen with high probability so long as none of $p,q$ or $pq$ are dominated by a small number of bins. In particular, for $\u03f5$ large, it would be sufficient to know that ${\parallel p\parallel}_{2}^{2},{\parallel q\parallel}_{2}^{2}\ll 1/(s\mathrm{log}(n))$. Although this might not be the case for the given $p$ and $q$ we can obtain it by flattening. The details of the analysis are given in Section 5.2.
For the streaming algorithm for closeness (Section 5.1), we take a somewhat different approach. We select a random hash function $h:[n]\to [m]$ and instead compare the distributions $h(p)$ and $h(q)$. It is not hard to show that if $p=q$ then $h(p)=h(q)$, and that if $p$ and $q$ are far in variation distance that $h(p)$ and $h(q)$ are likely somewhat far in variation distance. The algorithm can record the counts of the number of samples from each distribution in each bin in $O(m\mathrm{log}(n))$ samples and these counts are enough to run standard closeness testing algorithms.
1.4 Related work
Distribution Testing.
The field of distribution property testing [Batu et al.(2000)Batu, Fortnow, Rubinfeld, Smith, and White] has been extensively investigated in the past couple of decades, see, e.g., the surveys [Rubinfeld(2012), Canonne(2015), Goldreich(2017)]. A large body of the literature has focused on characterizing the sample size needed to test properties of arbitrary discrete distributions in the centralized setting. This broad inference task originates from the field of statistics and has been extensively studied in hypothesis testing [Neyman and Pearson(1933), Lehmann and Romano(2005)] with somewhat different formalism. The centralized regime is fairly well understood in a variety of settings: for many properties of interest there exist sampleefficient testers [Paninski(2008), Chan et al.(2014)Chan, Diakonikolas, Valiant, and Valiant, Valiant and Valiant(2014), Diakonikolas et al.(2015a)Diakonikolas, Kane, and Nikishkin, Acharya et al.(2015)Acharya, Daskalakis, and Kamath, Canonne et al.(2016)Canonne, Diakonikolas, Gouleakis, and Rubinfeld, Diakonikolas and Kane(2016), Diakonikolas et al.(2016)Diakonikolas, Gouleakis, Peebles, and Price, Canonne et al.(2018)Canonne, Diakonikolas, and Stewart, Goldreich(2017), Diakonikolas et al.(2017a)Diakonikolas, Gouleakis, Peebles, and Price, Batu and Canonne(2017), Diakonikolas et al.(2018)Diakonikolas, Kane, and Stewart, Canonne et al.(2017b)Canonne, Diakonikolas, Kane, and Stewart]. More recently, an emerging body of work has focused on leveraging a priori structure of the underlying distributions to obtain significantly improved sample complexities [Batu et al.(2004)Batu, Kumar, and Rubinfeld, Daskalakis et al.(2013)Daskalakis, Diakonikolas, Servedio, Valiant, and Valiant, Diakonikolas et al.(2015a)Diakonikolas, Kane, and Nikishkin, Diakonikolas et al.(2015b)Diakonikolas, Kane, and Nikishkin, Canonne et al.(2017a)Canonne, Diakonikolas, Kane, and Stewart, Daskalakis and Pan(2017), Daskalakis et al.(2018)Daskalakis, Dikkala, and Kamath, Diakonikolas et al.(2017c)Diakonikolas, Kane, and Nikishkin].
Distributed Statistical Inference.
There has been substantial recent interest in distributed estimation with communication constraints. A series of works [Zhang et al.(2013)Zhang, Duchi, Jordan, and Wainwright, Garg et al.(2014)Garg, Ma, and Nguyen, Braverman et al.(2016)Braverman, Garg, Ma, Nguyen, and Woodruff, Jordan et al.(2016)Jordan, Lee, and Yang, Diakonikolas et al.(2017b)Diakonikolas, Grigorescu, Li, Natarajan, Onak, and Schmidt, Han et al.(2018b)Han, Özgür, and Weissman, Han et al.(2018a)Han, Mukherjee, Özgür, and Weissman] studied distributed learning in both parametric and nonparametric settings obtaining (nearly) matching upper and lower bounds. Other learning tasks has been studied as well in the distributed setting, including regression [Zhu and Lafferty(2018)] and PCA [Kannan et al.(2014)Kannan, Vempala, and Woodruff, Liang et al.(2014)Liang, Balcan, Kanchanapally, and Woodruff].
Classical work in information theory [Cover(1969), Ahlswede and Csiszar(1986)] studies simple hypothesis testing problems with communication constraints (as opposed to the composite testing problems studied in our work). Their results and techniques appear to be orthogonal to ours. Two recent works [Acharya et al.(2018a)Acharya, Canonne, and Tyagi, Acharya et al.(2018b)Acharya, Canonne, and Tyagi] give algorithms and lower bounds for distribution testing in a distributed model where each machine holds a single sample and is allowed to communicate $\ll \mathrm{log}n$ bits of information. We note that this communication model is very different from ours: First, our focus is on the multiple samples per machine setting, where significant savings over the naive protocols is attainable. Moreover, we do not impose any restrictions on the amount of information communicated by any individual machine, and our goal is to minimize the total communication complexity of the protocol. Another recent work [Andoni et al.(2018)Andoni, Malkin, and Nosatzki] studies distributed closeness testing in a two party setting where each party has access to samples from one of the two distributions. This model is different than ours for two reasons: First, we consider a large number of machines (parties). Second, we do not make the assumption that each machine holds samples from different distributions. Finally, recent work [Fischer et al.(2018)Fischer, Meir, and Oshman] studied uniformity testing in the standard LOCAL and CONGEST models when each machine holds a single sample. We note that their results and techniques seem incomparable to ours, and in particular have no implications on the communication complexity of uniformity testing in our broadcast model. In the aforementioned models, there is an underlying graph whose nodes are the machines (players). In each round, every player can send information to all its neighbors. The objective is to minimize the number of rounds of the protocol, as opposed to the number of bits communicated. In particular, for the special case that the underlying graph is a clique, their algorithm does not achieve nontrivial communication complexity.
The work of [Chien et al.(2010)Chien, Ligett, and McGregor] studied distribution testing with limited memory focusing on streaming algorithms in the framework of the canonical tester [Valiant(2011)]. In particular, they show that for testing problems in this framework with sample complexity $f$, there are streaming algorithms with memory $m$ and sample complexity ${f}^{2}\cdot {2}^{O(\sqrt{\mathrm{log}(n)})}/m$. We note that this is competitive with our uniformity tester up to the ${2}^{O(\sqrt{\mathrm{log}(n)})}$ factor, but does substantially worse than our closeness tester for small $m$. They also consider another class of streaming algorithms, when the number of samples is large enough to learn the distribution in question, and when the problem of computing empirical distances has an efficient streaming algorithm. This does not compare favorably to our algorithms, which always use sublearning sample complexity.
1.5 Organization
The structure of this paper is as follows: After some preliminaries in Section 2, in Section 3 we present our bipartite collision tester and its implications to memory efficient and distributed uniformity testing. Section 4 presents our memory and communication lower bounds for uniformity testing. In Section 5, we give our upper bounds for closeness testing. Finally, we conclude in Section 6 with a set of open problems for future work.
2 Preliminaries
In this section, we introduce the mathematical notation and background necessary to state and prove our results in the following sections.
Notation We write $[n]$ to denote the set $\{1,\mathrm{\dots},n\}$. We consider discrete distributions over $[n]$, which are functions $p:[n]\to [0,1]$ such that ${\sum}_{i=1}^{n}{p}_{i}=1.$ We use the notation ${p}_{i}$ to denote the probability of element $i$ in distribution $p$. The ${\mathrm{\ell}}_{1}$ (resp. ${\mathrm{\ell}}_{2}$) norm of a distribution is identified with the ${\mathrm{\ell}}_{1}$ (resp. ${\mathrm{\ell}}_{2}$) norm of the corresponding vector, i.e., ${\parallel p\parallel}_{1}={\sum}_{i=1}^{n}{p}_{i}$ and ${\parallel p\parallel}_{2}=\sqrt{{\sum}_{i=1}^{n}{p}_{i}^{2}}$. The ${\mathrm{\ell}}_{1}$ (resp. ${\mathrm{\ell}}_{2}$) distance between (pseudo)distributions $p$ and $q$ is defined as the the ${\mathrm{\ell}}_{1}$ (resp. ${\mathrm{\ell}}_{2}$) norm of the vector of their difference, i.e., ${\parallel pq\parallel}_{1}={\sum}_{i=1}^{n}{p}_{i}{q}_{i}$ and ${\parallel pq\parallel}_{2}=\sqrt{{\sum}_{i=1}^{n}{({p}_{i}{q}_{i})}^{2}}$.
For a random variable $X$, we denote by $\mathbf{E}[X]$ its expectation, $\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}[X]$ its variance, and $\mathrm{\mathbf{P}\mathbf{r}}[\mathcal{E}]$ will denote the probability of event $\mathcal{E}$. Sometimes we will use the notation ${\mathbf{E}}_{D}[\cdot ],{\mathrm{\mathbf{P}\mathbf{r}}}_{D}[\cdot ]$ to make the underlying distribution explicit.
Distribution Testing Distribution property testing studies the following family of problems: given sample access to one or more unknown distributions, determine whether they satisfy some global property or are “far” from satisfying the property. In this work, we study the properties of identity testing (goodness of fit) and closeness testing (twosample testing) between two distributions.
[Identity Testing/Uniformity Testing] The identity testing problem is the following: Given samples from an unknown distribution $p$ on $[n]$, a known distribution $q$ on $[n]$, and a parameter $$, we want to distinguish, with probability at least $2/3$, between the cases that $p=q$ versus ${\parallel pq\parallel}_{1}\ge \u03f5$. The special case corresponding to $q={U}_{n}$, the uniform distribution on $[n]$, is the problem of uniformity testing.
[Closeness Testing] The closeness testing problem is the following: Given samples from two unknown distributions $p,q$ on $[n]$, and a parameter $$, we want to distinguish, with probability at least $2/3$, between the cases that $p=q$ versus ${\parallel pq\parallel}_{1}\ge \u03f5$.
3 Communication and Memory Efficient Uniformity Testing
In this section, we design our protocols for uniformity testing. In Section 3.1, we start with our bipartite uniformity tester. In Section 3.2, we give our streaming uniformity tester, which follows as an application of our bipartite uniformity tester. In Section 3.3, we give our first distributed uniformity tester, which is an instantiation of our bipartite collision tester and performs well when the number of samples per machine $\mathrm{\ell}$ is not very large. For the complementary setting that $\mathrm{\ell}$ is large, we give a different protocol in Section 3.4.
3.1 Testing Uniformity via Bipartite Collisions
Our bipartite collisionbased tester is described in pseudocode below:
Algorithm BipartiteCollisionUniformity$\mathrm{(}p\mathrm{,}n\mathrm{,}\u03f5\mathrm{)}$ Input: Sample access to distribution $p$ over $[n]$ and $\u03f5>0$. Output: “YES” if $p={U}_{n}$; “NO” if ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5.$ 1. Draw a multiset ${S}_{1}$ of ${N}_{1}$ i.i.d. samples from $p$. 2. For all $j\in [n]$ compute ${a}_{j}=\{s\in {S}_{1}:s=j\}$, i.e., the multiplicity of $j\in [n]$ in ${S}_{1}$. 3. If ${\mathrm{max}}_{j\in [n]}{a}_{j}>10$, return “NO”. Otherwise, continue with next step. 4. Draw a multiset ${S}_{2}$ of ${N}_{2}$ i.i.d. samples from $p$. For $k\in [{N}_{2}]$, let ${b}_{k}$ be the number of times that the $k$th sample in ${S}_{2}$ appears in ${S}_{1}$. 5. Let $Z=(1/{N}_{2}){\sum}_{k=1}^{{N}_{2}}{b}_{k}$ and $T\stackrel{\mathrm{def}}{=}\frac{{N}_{1}}{n}(1+\frac{{\u03f5}^{2}}{50})$. 6. If $Z\ge T$ return “NO”; otherwise, return “YES”.
The main result of this section is the following theorem:
Suppose that ${N}_{1},{N}_{2}$ satisfy the following conditions: (i) $\mathrm{\Omega}({\u03f5}^{6})={N}_{1}\le {n}^{9/10}$ and ${N}_{1}\cdot {N}_{2}=\mathrm{\Omega}(n/{\u03f5}^{4})$, where the implied constants in the $\mathrm{\Omega}(\cdot )$ are sufficiently large. Then the algorithm BipartiteCollisionUniformity distinguishes between the cases that $p={U}_{n}$ versus ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ with probability at least $2/3$.
This section is devoted to the proof of Theorem 3.1. We start with the following definition: {definition}[Probability Mass of Multiset] Let $p$ be a discrete distribution over $[n]$ and $S$ be a multiset of elements in $[n]$. We define the probability mass of the multiset $S$ as follows: $p(S)\stackrel{\mathrm{def}}{=}{\sum}_{j=1}^{n}{a}_{j}{p}_{j}$, where ${a}_{j}$ is the number of occurrences of $j\in [n]$ in $S$.
It should be noted that we will use the above quantity for $S$ being a multiset of i.i.d. samples from the distribution $p$. In this case, $p(S)$ is a random variable satisfying the following:
Claim \thetheorem
Let $S$ be a multiset of $m$ i.i.d. samples from the distribution $p$ on $\mathrm{[}n\mathrm{]}$. Then, we have that (i) ${\mathrm{E}}_{S}\mathit{}\mathrm{[}p\mathit{}\mathrm{(}S\mathrm{)}\mathrm{]}\mathrm{=}m\mathrm{\cdot}{\mathrm{\parallel}p\mathrm{\parallel}}_{\mathrm{2}}^{\mathrm{2}}$ and (ii) ${\mathrm{Var}}_{S}\mathit{}\mathrm{[}p\mathit{}\mathrm{(}S\mathrm{)}\mathrm{]}\mathrm{=}m\mathrm{\cdot}\mathrm{(}{\mathrm{\parallel}p\mathrm{\parallel}}_{\mathrm{3}}^{\mathrm{3}}\mathrm{}{\mathrm{\parallel}p\mathrm{\parallel}}_{\mathrm{2}}^{\mathrm{4}}\mathrm{)}\mathrm{.}$
By definition, $p(S)\stackrel{\mathrm{def}}{=}{\sum}_{j=1}^{n}{a}_{j}{p}_{j}$, where ${a}_{j}\sim \mathrm{Binomial}(m,{p}_{j})$, $j\in [n]$. For the expected value, we can write: ${\mathbf{E}}_{S}[p(S)]={\sum}_{j=1}^{n}{\mathbf{E}}_{S}[{a}_{j}]{p}_{j}={\sum}_{j=1}^{n}(m{p}_{j}){p}_{j}=m\cdot {\sum}_{j=1}^{n}{p}_{j}^{2}=m\cdot {\parallel p\parallel}_{2}^{2}$. To calculate the variance, we note that $p(S)$ can be equivalently expressed as $p(S)={\sum}_{i=1}^{m}{r}_{i}$, where for $i\in [m]$ we have that ${r}_{i}={p}_{j}$ with probability ${p}_{j}$, for $j\in [n]$. Note that the ${r}_{i}$’s are i.i.d. random variables and that ${\mathbf{E}}_{S}[{r}_{i}]={\parallel p\parallel}_{2}^{2}$, ${\mathbf{E}}_{S}[{r}_{i}^{2}]={\parallel p\parallel}_{3}^{3}$. Therefore, we obtain that ${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{S}[p(S)]={\sum}_{i=1}^{m}{\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{S}[{r}_{i}]=m\cdot ({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4}).$ This completes the proof of Claim 3.1.
We now proceed to establish the completeness and soundness of our tester.
Completeness Analysis
We will show that if $p={U}_{n}$, then the tester outputs “YES” with probability at least $2/3$. We start by noting that it is very unlikely that the tester rejects in Step 3.
Claim \thetheorem
Let $\mathrm{E}\stackrel{\mathrm{def}}{\mathrm{=}}\mathrm{\{}{S}_{\mathrm{1}}\mathrm{:}{\mathrm{max}}_{j\mathrm{\in}\mathrm{[}n\mathrm{]}}\mathit{}{a}_{j}\mathrm{\le}\mathrm{10}\mathrm{\}}$. For ${N}_{\mathrm{1}}\mathrm{\le}{n}^{\mathrm{9}\mathrm{/}\mathrm{10}}$, we have that ${\mathrm{Pr}}_{{S}_{\mathrm{1}}}\mathit{}\mathrm{[}\mathrm{E}\mathrm{]}\mathrm{\ge}\mathrm{19}\mathrm{/}\mathrm{20}$.
The probability that there exists some domain element in $[n]$ that appears at least $k$ times in ${S}_{1}$, where ${S}_{1}={N}_{1}$, is at most $n\cdot \left(\genfrac{}{}{0pt}{}{{N}_{1}}{k}\right){n}^{k}\le n\cdot \frac{{N}_{1}^{k}}{k!{n}^{k}}$. By our assumption that ${N}_{1}\le {n}^{9/10}$, for $k=10$ the above probability is at most $1/k!$, which gives the claim.
We proceed to analyze the behavior of the random variable $Z$ defining our test statistic in Step 5. Note that $Z$ is the empirical estimate of $p({S}_{1})$ based on the multiset of samples ${S}_{2}$. Indeed, denoting by ${({\widehat{p}}_{j})}^{{S}_{2}}$ the empirical probability of $j\in [n]$ based on ${S}_{2}$, then we have that $Z=(1/{N}_{2})\cdot {\sum}_{k=1}^{{N}_{2}}{b}_{k}={\sum}_{j=1}^{n}{a}_{j}\cdot {({\widehat{p}}_{j})}^{{S}_{2}}$. We have the following simple claim:
Claim \thetheorem
Let $p$ be any distribution over $\mathrm{[}n\mathrm{]}$. Then we have that: (i) ${\mathrm{E}}_{{S}_{\mathrm{2}}}\mathit{}\mathrm{[}Z\mathrm{]}\mathrm{=}p\mathit{}\mathrm{(}{S}_{\mathrm{1}}\mathrm{)}$ and (ii) ${\mathrm{Var}}_{{S}_{\mathrm{2}}}\mathit{}\mathrm{[}Z\mathrm{]}\mathrm{=}\mathrm{(}\mathrm{1}\mathrm{/}{N}_{\mathrm{2}}\mathrm{)}\mathrm{\cdot}\mathrm{\left(}{\mathrm{\sum}}_{j\mathrm{=}\mathrm{1}}^{n}{a}_{j}^{\mathrm{2}}\mathit{}{p}_{j}\mathrm{}{p}^{\mathrm{2}}\mathit{}\mathrm{(}{S}_{\mathrm{1}}\mathrm{)}\mathrm{\right)}$.
Since $Z={\sum}_{j=1}^{n}{a}_{j}\cdot {({\widehat{p}}_{j})}^{{S}_{2}}$ and ${\mathbf{E}}_{{S}_{2}}[{({\widehat{p}}_{j})}^{{S}_{2}}]={p}_{j}$, we get that ${\mathbf{E}}_{{S}_{2}}[Z]={\sum}_{j=1}^{n}{a}_{j}\cdot {p}_{j}=p({S}_{1})$. To calculate the variance, we use the equivalent definition of $Z=(1/{N}_{2})\cdot {\sum}_{k=1}^{{N}_{2}}{b}_{k}$, where for each $k\in [{N}_{2}]$ the i.i.d. random variables ${b}_{k}$ are defined as follows: ${b}_{k}={a}_{j}$ with probability ${p}_{j}$, for $j\in [n]$. It follows that ${\mathbf{E}}_{{S}_{2}}[{b}_{k}]={\sum}_{j=1}^{n}{a}_{j}{p}_{j}=p({S}_{1})$ and ${\mathbf{E}}_{{S}_{2}}[{b}_{k}^{2}]={\sum}_{j=1}^{n}{a}_{j}^{2}{p}_{j}$. Therefore, we get that ${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{2}}[Z]=(1/N_{2}{}^{2})\cdot {N}_{2}\cdot {\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{2}}[{b}_{1}]=(1/{N}_{2})\cdot ({\sum}_{j=1}^{n}{a}_{j}^{2}{p}_{j}{p}^{2}({S}_{1}))$. This completes the proof.
We note that Claim 3.1 will be useful both in the completeness and the soundness cases.
To establish the correctness of the tester in the completeness case, it suffices to show that ${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z>T]\le 1/3$. Since the event $\mathcal{E}$ occurs with high constant probability over ${S}_{1}$, by a union bound, it suffices to show that ${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z>T\mid \mathcal{E}]\le 1/10$. An application of Chebyshev’s inequality yields that
$${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z{\mathbf{E}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E}]>\gamma \mid \mathcal{E}]\le {\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E}]/{\gamma}^{2}.$$  (1) 
Note that in the completeness case ($p={U}_{n}$) we have that $p({S}_{1})={N}_{1}/n$ deterministically over ${S}_{1}$. Therefore, by Claim 3.1 (i), we get that ${\mathbf{E}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E}]={\mathbf{E}}_{{S}_{2}}[Z]=p({S}_{1})={N}_{1}/n$. Similarly, we obtain that
${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E}]$  $=$  ${\mathbf{E}}_{{S}_{1}\mid \mathcal{E}}\left[{\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{2}}[Z{S}_{1}]\right]+{\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1}\mid \mathcal{E}}\left[{\mathbf{E}}_{{S}_{2}}[Z]\right]$  
$\le $  $(1/{N}_{2})\cdot \underset{{S}_{1}\in \mathcal{E}}{\mathrm{max}}{\displaystyle \sum _{j=1}^{n}}{a}_{j}^{2}{p}_{j}+0$  
$\le $  $(10/{N}_{2})\cdot p({S}_{1})+0=10{N}_{1}/({N}_{2}\cdot n),$ 
where the second line uses Claim 3.1 (ii) and the fact that ${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1}\mid \mathcal{E}}\left[{\mathbf{E}}_{{S}_{2}}[Z]\right]=0$, and the third line follows from the definition of $\mathcal{E}$. By setting $\gamma \stackrel{\mathrm{def}}{=}({\u03f5}^{2}/100){\mathbf{E}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E}]=({\u03f5}^{2}/100)p({S}_{1})$, the RHS of (1) is at most $O\left(n/({\u03f5}^{4}\cdot {N}_{1}\cdot {N}_{2})\right)$. Recalling our assumption that ${N}_{1}\cdot {N}_{2}=\mathrm{\Omega}(n/{\u03f5}^{4})$ for a sufficiently large constant in the $\mathrm{\Omega}()$, we get that with probability at least $9/10$ we have that $$. This proves the completeness of our tester.
Soundness Analysis
We will show that if ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ for $\u03f5$ satisfying ${N}_{1}=\mathrm{\Omega}(1/{\u03f5}^{6})$, where the constant in $\mathrm{\Omega}()$ is sufficiently large, then the tester outputs “NO” with probability at least $2/3$. The technical part of the soundness proof involves showing that ${\mathbf{E}}_{{S}_{2}}[Z]=p({S}_{1})$ will be significantly larger than its value of $m/n$ in the completenesss case. Specifically, we show the following:
Let $\mathcal{F}\stackrel{\mathrm{def}}{=}\{{S}_{1}:p({S}_{1})\ge (1+{\u03f5}^{2}/40)\cdot ({N}_{1}/n)\}$. If ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ and ${N}_{1}=\mathrm{\Omega}(1/{\u03f5}^{6})$, then ${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1}}\left[\mathcal{F}\right]\ge 9/10$. {proof} The proof proceeds by case analysis. First, we consider the case that the distribution $p$ assigns sufficient probability on heavy elements. This case turns out to be fairly easy to handle. The complementary case that $p$ has a small amount of mass on heavy elements requires a more elaborate argument. Let $\theta \stackrel{\mathrm{def}}{=}{10}^{4}/({\u03f5}^{2}n)$ and let $H=H(p)\stackrel{\mathrm{def}}{=}\{i\in [n]\mid {p}_{i}\ge \theta \}$ be the set of heavy bins. We consider the following cases:
[Case I: $p\mathbf{}\mathrm{(}H\mathrm{)}\mathrm{=}{\mathrm{\sum}}_{i\mathrm{\in}H}{p}_{i}\mathrm{\ge}{\u03f5}^{\mathrm{2}}\mathrm{/}\mathrm{1000}$.] Let $W={S}_{1}\cap H$. Note that ${\mathbf{E}}_{{S}_{1}}[W]={N}_{1}\cdot p(H)\ge {N}_{1}{\u03f5}^{2}/1000$. By a multiplicative Chernoff bound, for $\delta =1/3$, we get that
$$ 
where we used the fact that ${N}_{1}=\omega (1/{\u03f5}^{2})$. That is, with probability at least $9/10$, the multiset ${S}_{1}$ will contain at least ${N}_{1}{\u03f5}^{2}/150$ samples from the set $H$. If this happens, then we have that
$$p({S}_{1})>({N}_{1}{\u03f5}^{2}/1500)\cdot \theta >(6{N}_{1})/n>(1+{\u03f5}^{2}/40)\cdot ({N}_{1}/n)$$ 
which proves Case I.
[Case II: $p\mathbf{}\mathrm{(}H\mathrm{)}\mathrm{=}{\mathrm{\sum}}_{i\mathrm{\in}H}{p}_{i}\mathrm{\le}{\u03f5}^{\mathrm{2}}\mathrm{/}\mathrm{100}$.] Let $\overline{H}\stackrel{\mathrm{def}}{=}[n]\setminus H$ and ${S}_{1}^{\prime}={S}_{1}\cap \overline{H}$, i.e., ${S}_{1}^{\prime}$ contains the samples in ${S}_{1}$ that correspond to light elements of $p$. Clearly, we have that $p({S}_{1})\ge p({S}_{1}^{\prime})$. We will show that ${\mathrm{Pr}}_{{S}_{1}}[p({S}_{1}^{\prime})\ge (1+{\u03f5}^{2}/40)\cdot ({N}_{1}/n)]\ge 9/10.$
Since $p(H)\le {\u03f5}^{2}/1000$, with probability at least $1{\u03f5}^{2}/1000$, a given sample in ${S}_{1}$ will also be in ${S}_{1}^{\prime}$. So, if ${N}_{1}^{\prime}={S}_{1}^{\prime}$ we have that ${\mathbf{E}}_{{S}_{1}}[{N}_{1}^{\prime}]\ge {N}_{1}(1{\u03f5}^{2}/1000)$. By Markov’s inequality applied to ${N}_{1}{N}_{1}^{\prime}$, with probability at least $19/20$ over ${S}_{1}$, we have that ${N}_{1}^{\prime}\ge {N}_{1}(1{\u03f5}^{2}/50)$. We will henceforth condition on this event.
To bound $p({S}_{1}^{\prime})$ from below, we consider the normalized distribution, ${p}^{\prime}$, over $[n]$ obtained from $p$ after removing its heavy elements. That is, for $i\in \overline{H}$, ${p}_{i}^{\prime}={p}_{i}/(1p(H))$; and for $i\in H$, ${p}_{i}^{\prime}=0$. Note that ${S}_{1}^{\prime}$ consists of ${N}_{1}^{\prime}$ elements drawn i.i.d. from ${p}^{\prime}$. By definition, we have that $p({S}_{1}^{\prime})=(1p(H)){p}^{\prime}({S}_{1}^{\prime})$. We will bound ${p}^{\prime}({S}_{1}^{\prime})$ by applying Chebyshev’s inequality.
We start by noting that ${p}^{\prime}$ is also far from being uniform:
Claim \thetheorem
We have that ${\mathrm{\parallel}{p}^{\mathrm{\prime}}\mathrm{}{U}_{n}\mathrm{\parallel}}_{\mathrm{1}}\mathrm{\ge}\u03f5\mathrm{/}\mathrm{3}$.
Since ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$, we have that ${\sum}_{j\in [n]:{p}_{j}>1/n}{p}_{j}1/n>\u03f5/2$. Since $$, it follows that $$. Noting that if $$, then $$ gives the claim. By Chebyshev’s inequality, we can write:
$${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime}){\mathbf{E}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]>\gamma ]\le {\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]/{\gamma}^{2},$$  (2) 
where we will set $\gamma \stackrel{\mathrm{def}}{=}({\u03f5}^{2}/20)\cdot {\mathbf{E}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]$. By Claim 3.1, we have that ${\mathbf{E}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]={N}_{1}^{\prime}\cdot {\parallel {p}^{\prime}\parallel}_{2}^{2}$, and ${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]={N}_{1}^{\prime}\cdot ({\parallel {p}^{\prime}\parallel}_{3}^{3}{\parallel {p}^{\prime}\parallel}_{2}^{4})$. In the following claim, we bound the variance from above:
Claim \thetheorem
We have that $$.
We have that $$. We will show that ${\parallel {p}^{\prime}\parallel}_{\mathrm{\infty}}\le 2\theta $ from which the claim follows. Indeed, note that the nonzero probability values of ${p}^{\prime}$ are ${p}_{i}^{\prime}={p}_{i}/(1p(H))$, for $i\notin H$. Since ${p}_{i}\le \theta $ and $$, we get the desired bound on ${\parallel {p}^{\prime}\parallel}_{\mathrm{\infty}}$ and the claim follows. The RHS of (2) can be bounded by $O({\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]/({\u03f5}^{4}{\mathbf{E}}_{{S}_{1}^{\prime}}{[{p}^{\prime}({S}_{1}^{\prime})]}^{2}))=O(1/({N}_{1}^{\prime}\cdot {\u03f5}^{6}))$, where we used our bounds on the first two moments and the fact that ${\parallel {p}^{\prime}\parallel}_{2}^{2}\ge 1/n$. Using the condition that ${N}_{1}=\mathrm{\Omega}(1/{\u03f5}^{6})$ and the fact that ${N}_{1}^{\prime}\ge {N}_{1}\cdot (1O({\u03f5}^{2}))$, the above probability is at most $1/20$.
We now show that if ${p}^{\prime}({S}_{1}^{\prime}){\mathbf{E}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]\le \gamma $ the event $\mathcal{F}$ holds. By the definition of $\gamma $ and the fact ${\mathbf{E}}_{{S}_{1}^{\prime}}[{p}^{\prime}({S}_{1}^{\prime})]={N}_{1}^{\prime}\cdot {\parallel {p}^{\prime}\parallel}_{2}^{2}$, this is equivalent to ${p}^{\prime}({S}_{1}^{\prime})>(1{\u03f5}^{2}/20)\cdot {N}_{1}^{\prime}\cdot {\parallel {p}^{\prime}\parallel}_{2}^{2}$. Claim 3.1 implies that ${\parallel {p}^{\prime}\parallel}_{2}^{2}\ge (1/n)\cdot (1+{\u03f5}^{2}/9)$, and therefore we get that
$${p}^{\prime}({S}_{1}^{\prime})>(1{\u03f5}^{2}/20)\cdot (1{\u03f5}^{2}/50)\cdot ({N}_{1}/n)\cdot (1+{\u03f5}^{2}/9)>({N}_{1}/n)\cdot (1+{\u03f5}^{2}/35),$$ 
where we used our lower bound on ${N}_{1}^{\prime}$. Finally, we have that
$$p({S}_{1})\ge p({S}_{1}^{\prime})=(1p(H)){p}^{\prime}({S}_{1}^{\prime})\ge (1{\u03f5}^{2}/1000)\cdot ({N}_{1}/n)\cdot (1+{\u03f5}^{2}/35)>({N}_{1}/n)\cdot (1+{\u03f5}^{2}/40),$$ 
and the proof of Lemma 3.1 is complete.
To establish correctness in the soundness case, it suffices to show that ${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z\le T]\le 1/3$. To show this, we condition on any ${S}_{1}$ such that the events $\mathcal{E}$ and $\mathcal{F}$ hold. Note that if $\mathcal{E}$ does not occur, then our tester correctly rejects. By Lemma 3.1 above, $\mathcal{F}$ holds with probability at least $9/10$ over ${S}_{1}$. Hence, by a union bound, it suffices to show that ${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z\le T\mid \mathcal{E},\mathcal{F}]\le 1/10$.
An application of Chebyshev’s inequality for $\gamma =({\u03f5}^{2}/100){\mathbf{E}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E},\mathcal{F}]$ yields that
$${\mathrm{\mathbf{P}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z{\mathbf{E}}_{{S}_{2}}[Z]>\gamma \mid \mathcal{E},\mathcal{F}]\le {\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{1},{S}_{2}}[Z\mid \mathcal{E},\mathcal{F}]/{\gamma}^{2}.$$  (3) 
By Claim 3.1, we have that ${\mathbf{E}}_{{S}_{2}}[Z]=p({S}_{1})$ and ${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{{S}_{2}}[Z]=(1/{N}_{2})\cdot \left({\sum}_{j=1}^{n}{a}_{j}^{2}{p}_{j}{p}^{2}({S}_{1})\right)$. The same argument as in the completeness case gives that $$ By our choice of $\gamma $ and our bound on the variance the righthand side of (3) is at most $O\left(1/({N}_{2}{\u03f5}^{4}p({S}_{1}))\right)$. Recalling our assumption that ${N}_{1}\cdot {N}_{2}=\mathrm{\Omega}(n/{\u03f5}^{4})$ and the fact that $p({S}_{1})\ge {N}_{1}/n$ (by Lemma 3.1, since $\mathcal{F}$ occurs), it follows that this probability is at most $1/10$. By Lemma 3.1 we have that $p({S}_{1})>({N}_{1}/n)\cdot (1+{\u03f5}^{2}/40)$. Therefore, with probability at least $8/10$ (by a union bound on the two error events), we have that $Z>({N}_{1}/n)\cdot (1+{\u03f5}^{2}/50)$. This establishes the soundness case and completes the proof of Theorem 3.1.
3.2 Memory Efficient Uniformity Testing
In this section, we show how our bipartite collision tester can be used to obtain a memory efficient single pass streaming algorithm. Our memory efficient tester is described in pseudocode below:
Algorithm StreamingUniformity$\mathrm{(}p\mathrm{,}n\mathrm{,}m\mathrm{,}\u03f5\mathrm{)}$ Input: Sample access to distribution $p$ over $[n]$, memory bound $m$, and $\u03f5>0$. Output: “YES” if $p={U}_{n}$; “NO” if ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5.$ 1. Draw a multiset ${S}_{1}$ of ${N}_{1}\stackrel{\mathrm{def}}{=}m/(2\mathrm{log}n)$ i.i.d. samples from $p$. Store ${S}_{1}$ in memory. 2. For all $j\in [n]$ compute ${a}_{j}=\{s\in {S}_{1}:s=j\}$, i.e., the multiplicity of $j\in [n]$ in ${S}_{1}$. 3. If ${\mathrm{max}}_{j\in [n]}{a}_{j}>10$, return “NO”. Otherwise, continue with next step. 4. Draw a multiset ${S}_{2}$ of ${N}_{2}\stackrel{\mathrm{def}}{=}\mathrm{\Theta}\left(n\mathrm{log}n/(m{\u03f5}^{4})\right)$ i.i.d. samples from $p$, for an appropriately large constant in $\mathrm{\Theta}(\cdot )$. For $k\in [{N}_{2}]$, let ${b}_{k}$ be the number of times that the $k$th sample in ${S}_{2}$ appears in ${S}_{1}$. Store the partial sum ${\sum}_{k}{b}_{k}$ in a single pass. 5. Let $Z=(1/{N}_{2}){\sum}_{k=1}^{{N}_{2}}{b}_{k}$ and $T\stackrel{\mathrm{def}}{=}\frac{{N}_{1}}{n}(1+\frac{{\u03f5}^{2}}{50})$. 6. If $Z\ge T$ return “NO”; otherwise, return “YES”.
The following theorem is essentially a corollary of Theorem 3.1 and characterizes the performance of the above algorithm:
Suppose that $m\ge \mathrm{\Omega}(\mathrm{log}n/{\u03f5}^{6})$ and $m\le \stackrel{~}{O}({n}^{9/10})$. Algorithm StreamingUniformity is a single pass streaming algorithm using at most $m$ bits of memory, and distinguishes between the cases that $p={U}_{n}$ versus ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ with probability at least $2/3$. {proof} The correctness of StreamingUniformity as a uniformity testing algorithm follows from Theorem 3.1 and our choice of parameters. It is straightforward to check that the assumptions of the latter theorem are satisfied for our choice of ${N}_{1}$ and ${N}_{2}$.
It is also easy to argue that the algorithm is implementable in the single pass streaming model with at most $m$ bits of memory. Step 1 of the algorithm uses ${N}_{1}\mathrm{log}n\le m/2$ bits of memory. We claim that Step 4 can be implemented in a single pass with at most $\mathrm{log}{N}_{2}+4$ bits of memory. Indeed, since no element of $[n]$ appears in ${S}_{1}$ more than $10$ times (since the algorithm did not reject in Step 3), each ${b}_{k}$ is at most $10$. Therefore, ${\sum}_{k=1}^{{N}_{2}}{b}_{k}\le 10{N}_{2}$, and thus the sum ${\sum}_{k=1}^{{N}_{2}}{b}_{k}$ can be stored with $\mathrm{log}{N}_{2}+4$ bits of memory. In summary, the total memory used by our algorithm is at most $m/2+\mathrm{log}{N}_{2}+4$. By our assumption that $m\ge \mathrm{\Omega}(\mathrm{log}n/{\u03f5}^{6})$, it follows that ${N}_{2}\le {\u03f5}^{2}n$ or $$. Therefore, $\mathrm{log}{N}_{2}\ll m$ which completes the proof of Theorem 3.2.
3.3 Distributed Uniformity Testing for Small Number of Samples per Machine
Let $\mathrm{\ell}$ denote the total number of samples from $p$ possessed by each machine. When $\mathrm{\ell}=\stackrel{~}{O}({n}^{1/3}/{\u03f5}^{4/3})$, we use the following tester, which can be viewed as an instantiation of our bipartite collision tester.
Algorithm I DistributedBipartiteUniformity$\mathrm{(}p\mathrm{,}n\mathrm{,}\mathrm{\ell}\mathrm{,}\u03f5\mathrm{)}$ Input: Unbounded number of machines, each with $\mathrm{\ell}$ i.i.d. samples from $p$ and $\u03f5>0$. Output: “YES” if $p={U}_{n}$; “NO” if ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5.$ 1. The referee asks ${m}_{1}=\mathrm{\Theta}\left((1/({\u03f5}^{2}{\mathrm{\ell}}^{3/2}))\sqrt{n/\mathrm{log}n}\right)$ machines to reveal all their samples. Let ${S}_{1}$ be the resulting multiset of samples from $p$. 2. For all $j\in [n]$ the referee computes ${a}_{j}=\{s\in {S}_{1}:s=j\}$, i.e., the multiplicity of $j\in [n]$ in ${S}_{1}$. 3. If ${\mathrm{max}}_{j\in [n]}{a}_{j}>10$, the referee returns “NO”. Otherwise, we continue with next step. 4. The referee queries a new set of ${m}_{2}=\mathrm{\Theta}(\frac{n}{{\u03f5}^{4}{\mathrm{\ell}}^{2}{m}_{1}})$ machines, indexed by $k\in [{m}_{2}]$, in increasing order of $k$, to report the value ${b}_{k}={\sum}_{i=1}^{\mathrm{\ell}}{a}_{{s}_{i}^{k}}$ corresponding to their sample set ${S}_{2}^{k}={\{{s}_{i}^{k}\}}_{i=1}^{\mathrm{\ell}}$. Note that ${b}_{k}$ is the number of collisions of ${S}_{2}^{k}$ with ${S}_{1}$. 5. For $t\in [{m}_{2}]$, define ${B}_{t}={\sum}_{k=1}^{t}{b}_{k}$. Let $Z={B}_{{m}_{2}}/(\mathrm{\ell}\cdot {m}_{2})$ and $T\stackrel{\mathrm{def}}{=}\frac{{m}_{1}\cdot \mathrm{\ell}}{n}(1+{\u03f5}^{2}/50)$. 6. The referee computes ${B}_{t}$ in increasing order of $t\in [{m}_{2}]$. If for some $t\in [{m}_{2}]$, ${B}_{t}\ge \mathrm{\ell}\cdot {m}_{2}\cdot T$, we terminate and returns “NO”. Otherwise, we have that $$ and we return “YES”.
The following theorem characterizes the performance of the above algorithm:
Suppose that $\mathrm{\Omega}(1/{\u03f5}^{6})\le {m}_{1}\cdot \mathrm{\ell}\le O({n}^{9/10})$. Algorithm DistributedBipartiteUniformity draws a total of $O\left((1/{\u03f5}^{2})\sqrt{n\cdot \mathrm{\ell}\cdot \mathrm{log}n}\right)$ samples from $p$, uses at most $O\left((1/{\u03f5}^{2})\sqrt{(n/\mathrm{\ell})\cdot \mathrm{log}n}\right)$ bits of communication, and distinguishes between the cases that $p={U}_{n}$ versus ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ with probability at least $2/3$.
The correctness of DistributedBipartiteUniformity follows from Theorem 3.1 and our choice of parameters. It is straightforward to check that the assumptions of the latter theorem are satisfied for our choice of ${N}_{1}={m}_{1}\cdot \mathrm{\ell}$ and ${N}_{2}={m}_{2}\cdot \mathrm{\ell}$.
It is also clear that the sample complexity of our algorithm is
$$({m}_{1}+{m}_{2})\cdot \mathrm{\ell}=O\left((1/{\u03f5}^{2})\sqrt{n/({\mathrm{\ell}}^{3}\mathrm{log}n)}+(1/{\u03f5}^{2})\sqrt{(n\mathrm{log}n)/\mathrm{\ell}}\right)\cdot \mathrm{\ell}=O\left((1/{\u03f5}^{2})\sqrt{n\cdot \mathrm{\ell}\cdot \mathrm{log}n}\right).$$ 
We now proceed to bound the communication complexity. Note that Step 1 uses ${m}_{1}\cdot \mathrm{\ell}\cdot \mathrm{log}n$ bits of communication. We claim that Step 6 can be implemented with $O({m}_{2})$ bits of communication. To achieve this, we transmit each ${b}_{k}$ in unary by sending ${b}_{k}$ many $1$’s followed by a $0$ and terminate the algorithm rejecting if the partial sum ${B}_{t}={\sum}_{k=1}^{t}{b}_{k}$, for some $t\in [{m}_{2}]$, exceeds the rescaled threshold $\mathrm{\ell}\cdot {m}_{2}\cdot T$. Since we use ${b}_{k}+1$ bits to encode each ${b}_{k}$, the number of bits of communication is bounded by ${\mathrm{max}}_{t}({B}_{t}+t)$, which is at most $\mathrm{\ell}\cdot {m}_{2}\cdot T+{m}_{2}$. We now show that $\mathrm{\ell}\cdot {m}_{2}\cdot T=O({m}_{2})$, which proves the desired communication upper bound. Note that by our choice of ${m}_{1},{m}_{2}$, we have that $\mathrm{\ell}\cdot {m}_{2}\cdot T=O(1/{\u03f5}^{4})$ and moreover ${m}_{2}>{m}_{1}\cdot \mathrm{\ell}=\mathrm{\Omega}(1/{\u03f5}^{6})$. Therefore, $\mathrm{\ell}\cdot {m}_{2}\cdot T\le {m}_{2}$, as desired. This completes the proof of Theorem 3.3.
3.4 Distributed Uniformity Testing for Large Number of Samples per Machine
In this section, we give our alternate distributed uniformity tester with improved communication complexity when the number of samples per machine is large.
When the number of samples per machine $\mathrm{\ell}$ satisfies $\mathrm{\ell}=\stackrel{~}{\mathrm{\Omega}}({n}^{1/3}/{\u03f5}^{4/3})$, we will use the following algorithm:
Algorithm II DistributedAggregateUniformity$\mathrm{(}p\mathrm{,}n\mathrm{,}\mathrm{\ell}\mathrm{,}\u03f5\mathrm{)}$ Input: Each machine has $\mathrm{\ell}$ samples from a distribution $p$ over $[n]$ and $\u03f5>0$. Output: “YES” if $p={U}_{n}$; “NO” if ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5.$ 1. The referee asks the first $m=\frac{12800\cdot n}{{\mathrm{\ell}}^{2}{\u03f5}^{4}}$ machines to reveal the number of collisions ${c}_{k}$, $k\in [m]$, each of them see in their $\mathrm{\ell}$ samples. 2. Compute the statistic $Z=(1/m){\sum}_{k=1}^{m}{c}_{k}$ and the Threshold $T=\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right)\frac{1+{\u03f5}^{2}/2}{n}$. 3. If $Z\ge T$ return “NO”; otherwise, return “YES”.
The following theorem characterizes the performance of the above algorithm:
The algorithm DistributedAggregateUniformity draws a total of $O\left(n/(\mathrm{\ell}{\u03f5}^{4})\right)$ samples from $p$, uses $O(\frac{n\mathrm{log}n}{{\mathrm{\ell}}^{2}{\u03f5}^{4}})$ bits of communication, and distinguishes between the cases that $p={U}_{n}$ versus ${\parallel p{U}_{n}\parallel}_{1}\ge \u03f5$ with probability at least $2/3$.
In this rest of this section, we prove Theorem 3.4.
First note that the sample complexity of our algorithm is $m\cdot \mathrm{\ell}=O(\frac{n}{\mathrm{\ell}{\u03f5}^{4}})$. Moreover, the communication complexity of our tester is $O(\frac{n}{{\mathrm{\ell}}^{2}{\u03f5}^{4}}\mathrm{log}({\mathrm{\ell}}^{2}))=O(\frac{n\mathrm{log}n}{{\mathrm{\ell}}^{2}{\u03f5}^{4}})$, since each of the $\mathrm{\Theta}(\frac{n}{{\mathrm{\ell}}^{2}{\u03f5}^{4}})$ players sends the number of their internal collisions, which can be at most $\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right)$.
We will compute the mean and variance of the statistic $Z$ and show that the uniform and nonuniform cases are wellseparated. Lemma 2.3 in [Diakonikolas et al.(2016)Diakonikolas, Gouleakis, Peebles, and Price] implies that:
$$\mathbf{E}[Z]=\frac{1}{m}\sum _{i=1}^{m}\mathbf{E}[{c}_{i}]=\mathbf{E}[{c}_{i}]=\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right){\parallel p\parallel}_{2}^{2}$$ 
and
$\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}[Z]={\displaystyle \frac{1}{{m}^{2}}}{\displaystyle \sum _{i=1}^{t}}\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}[{c}_{i}]$  $={\displaystyle \frac{{\mathrm{\ell}}^{2}{\u03f5}^{4}}{12800n}}\left[\left({\displaystyle \genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}}\right)({\parallel p\parallel}_{2}^{2}{\parallel p\parallel}_{2}^{4})+\mathrm{\ell}(\mathrm{\ell}1)(\mathrm{\ell}2)({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})\right]$  
$\le {\displaystyle \frac{{\mathrm{\ell}}^{2}{\u03f5}^{4}}{12800n}}\left[{\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}+{\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})\right].$ 
The following lemma, which is an adaptation of an analogous lemma in [Diakonikolas et al.(2016)Diakonikolas, Gouleakis, Peebles, and Price]), will give us the minimum number of samples per player required for the tester to work given our choice of parameters:
Let $\alpha $ satisfy ${\parallel p\parallel}_{2}^{2}=\frac{1+\alpha}{n}$ and $\sigma $ be the standard deviation of $Z$. The number of samples required by DistributedAggregateUniformity is at most
$$\mathrm{\ell}\le \sqrt{\frac{5\sigma n}{\alpha {\u03f5}^{2}/2}},$$ 
in order to get error probability at most $1/4$.
By Chebyshev’s inequality, we have that
$$\mathrm{\mathbf{P}\mathbf{r}}\left[\rightZ\mathbf{E}[Z]\ge k\sigma ]=\mathrm{\mathbf{P}\mathbf{r}}\left[\rightZ\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right)\parallel p{\parallel}_{2}^{2}\ge k\sigma ]\le \frac{1}{{k}^{2}},$$ 
where $\sigma \triangleq \sqrt{\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}[Z]}$.
We want $Z$ to be closer to its expected value than the threshold is to that expected value because when this occurs, the tester outputs the right answer. Furthermore, to achieve our desired probability of error of at most $1/4$, we want this to happen with probability at least $3/4$. So, we want
$$k\sigma \le \mathbf{E}[Z]T=\left\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right)\left({\parallel p\parallel}_{2}^{2}\frac{1+{\u03f5}^{2}/2}{n}\right)\right=\left(\genfrac{}{}{0pt}{}{\mathrm{\ell}}{2}\right)\alpha {\u03f5}^{2}/2/n.$$ 
For $\mathrm{\ell}$ larger than some small constant and $k=2$, the following slightly stronger condition for $\mathrm{\ell}$ suffices:
$$\sigma \le {\mathrm{\ell}}^{2}\cdot \frac{\alpha {\u03f5}^{2}/2}{5n}.$$ 
So, it suffices to have
$$\mathrm{\ell}\ge \sqrt{\frac{5\sigma n}{\alpha {\u03f5}^{2}/2}}.$$  (4) 
We might as well take the smallest number of samples per player $\mathrm{\ell}$ for which the tester works, which implies the desired inequality.
To complete the proof, we need to show that given enough samples there is a clear separation between the completeness and soundness cases regarding the value of our statistic.
By Lemma 3.4, it suffices to bound from above the variance ${\sigma}^{2}$. We proceed by case analysis based on whether the term ${\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}$ or ${\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})$ contributes more to the variance.
Case when ${\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}$ is Larger
We have the following lemma:
Let ${\parallel p\parallel}_{2}^{2}=(1+\alpha )/n$. Consider the completeness case when $\alpha =0$ and the soundness case when $\alpha \ge {\u03f5}^{2}$. If ${\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}$ contributes more to the variance, i.e., if
$${\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}\ge {\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4}),$$ 
then DistributedAggregateUniformity has error probability at most $1/4$ for any value of $\mathrm{\ell}$.
Suppose that ${\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}\ge {\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})$. Then ${\sigma}^{2}\le 2\frac{{\mathrm{\ell}}^{4}{\u03f5}^{4}}{12800n}{\parallel p\parallel}_{2}^{2}=\frac{{\mathrm{\ell}}^{4}{\u03f5}^{4}}{6400n}(1+\alpha )/n$. Substituting this into (4) gives:
$$\sqrt{\frac{5\sigma n}{\alpha {\u03f5}^{2}/2}}\le \frac{\mathrm{\ell}\u03f5{(1+\alpha )}^{1/4}}{4\sqrt{\alpha {\u03f5}^{2}/2}}.$$ 
One can show the latter inequality, using calculus to maximize the ratio: $\frac{\mathrm{\ell}\u03f5{(1+\alpha )}^{1/4}}{4\sqrt{\alpha {\u03f5}^{2}/2}}$ by varying $\alpha $. One gets that $\alpha ={\u03f5}^{2}$ maximizes the expression for $\alpha \in \{0\}\cup [{\u03f5}^{2},n1]$, since it is decreasing in the interval $[{\u03f5}^{2},n1]$ and also $\alpha ={\u03f5}^{2}$ gives a slightly larger value than $\alpha =0$. Thus, we get that:
$$\sqrt{\frac{5\sigma n}{\alpha {\u03f5}^{2}/2}}\le \mathrm{\ell}\cdot \frac{\u03f5{(1+{\u03f5}^{2})}^{1/4}}{4\sqrt{{\u03f5}^{2}/2}}\le \mathrm{\ell}\frac{{(1+{\u03f5}^{2})}^{1/4}}{2}\le \mathrm{\ell}$$ 
for any $$. Therefore, this completes the proof since the requirements of Lemma 3.4 are satisfied.
Case when ${\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})$ is Larger
In this case, we show the following: {lemma} Let ${\parallel p\parallel}_{2}^{2}=(1+\alpha )/n$. Consider the completeness case when $\alpha =0$ and the soundness case when $\alpha \ge {\u03f5}^{2}$. If ${\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})$ contributes more to the variance, i.e., if
$${\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})\ge {\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2},$$ 
then for any $\mathrm{\ell}\le \frac{16\sqrt{n}}{3{\u03f5}^{2}}$ in the completeness case and any $\mathrm{\ell}\le \frac{16\sqrt{n}}{3\alpha}$ in the soundness case, our tester DistributedAggregateUniformity achieves error probability at most $1/4$.
Suppose that ${\mathrm{\ell}}^{3}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})\ge {\mathrm{\ell}}^{2}{\parallel p\parallel}_{2}^{2}$. Then ${\sigma}^{2}\le 2\frac{{\mathrm{\ell}}^{5}{\u03f5}^{4}}{12800n}({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})$. Substituting this into (4) gives:
$$\mathrm{\ell}\ge \sqrt{\frac{5\sigma n}{\alpha {\u03f5}^{2}/2}}\ge \frac{{\mathrm{\ell}}^{5/4}\u03f5{n}^{1/4}{({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})}^{1/4}}{4\sqrt{\alpha {\u03f5}^{2}/2}}\iff $$ 
$$\mathrm{\ell}\le \frac{256{\alpha {\u03f5}^{2}/2}^{2}}{{\u03f5}^{4}n({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})}$$ 
Let us parameterize $p$ as ${p}_{i}=1/n+{a}_{i}$ for some vector $a=({a}_{1},\mathrm{\dots},{a}_{n})$. Then we have ${\parallel a\parallel}_{2}^{2}=\alpha /n$.
In the completeness case, the above sufficient condition always holds since the right hand side is infinite (i.e., ${\parallel p\parallel}_{3}^{3}={\parallel p\parallel}_{2}^{4}$). In the soundness case, we get the following sufficient condition:
$$\mathrm{\ell}\le \frac{256{(\alpha /2)}^{2}}{{\u03f5}^{4}n({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})}\mathit{\hspace{1em}}\text{(since}{\u03f5}^{2}\le \alpha \text{)}.$$ 
We also have that:
${\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4}$  $\le {\parallel p\parallel}_{3}^{3}{\displaystyle \frac{1}{{n}^{2}}}=\left[{\displaystyle \sum _{i=1}^{n}}{(1/n+{a}_{i})}^{3}\right]{\displaystyle \frac{1}{{n}^{2}}}$  
$=\left[{\displaystyle \frac{1}{{n}^{2}}}+{\displaystyle \frac{3}{{n}^{2}}}{\displaystyle \sum _{i=1}^{n}}{a}_{i}+{\displaystyle \frac{3}{n}}{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{2}+{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{3}\right]{\displaystyle \frac{1}{{n}^{2}}}$  
$={\displaystyle \frac{3}{{n}^{2}}}{\displaystyle \sum _{i=1}^{n}}{a}_{i}+{\displaystyle \frac{3}{n}}{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{2}+{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{3}$  
$={\displaystyle \frac{3}{n}}{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{2}+{\displaystyle \sum _{i=1}^{n}}{a}_{i}^{3}$  
$\le {\displaystyle \frac{3}{n}}{\parallel a\parallel}_{2}^{2}+{\parallel a\parallel}_{3}^{3}\le {\displaystyle \frac{3}{n}}{\parallel a\parallel}_{2}^{2}+{\parallel a\parallel}_{2}^{3}={\displaystyle \frac{3}{n}}(\alpha /n)+{(\alpha /n)}^{3/2}.$ 
We thus get:
$\frac{256{(\alpha /2)}^{2}}{{\u03f5}^{4}n({\parallel p\parallel}_{3}^{3}{\parallel p\parallel}_{2}^{4})}$  $\ge {\displaystyle \frac{256{(\alpha /2)}^{2}}{{\alpha}^{2}n(\frac{3}{n}(\alpha /n)+{(\alpha /n)}^{3/2})}}$  
$\ge {\displaystyle \frac{64}{n(\frac{3}{n}(\alpha /n)+{(\alpha /n)}^{3/2})}}$  
$\ge {\displaystyle \frac{64}{\frac{3\alpha}{n}+\frac{{\alpha}^{3/2}}{\sqrt{n}}}}$  
$\ge {\displaystyle \frac{64n}{3\alpha +{\alpha}^{3/2}\sqrt{n}}}$  
$\ge \mathrm{min}\{{\displaystyle \frac{64n}{3\alpha}},{\displaystyle \frac{64\sqrt{n}}{{\alpha}^{3/2}}}\}$  
$\ge {\displaystyle \frac{64\sqrt{n}}{3\alpha}}.$ 
Therefore, any $\mathrm{\ell}\le \frac{64\sqrt{n}}{3\alpha}$ satisfies the conditions of Lemma 3.4. Combining the above, we can see that our tester works for any value of $\mathrm{\ell}$ that is less than the sample complexity of the problem in the classical (nondistributed) model.
4 Communication and Memory Lower Bounds for Uniformity Testing
In this section, we prove our memory and communication lower bounds.
4.1 Background from Information Theory
For completeness, we start by recalling basic definitions from information theory. We will first define the entropy of a random variable: {definition} Let $X$ be a discrete random variable supported on $\{{x}_{1},\mathrm{\dots},{x}_{n}\}$ that has a probability mass function $p=({p}_{1},\mathrm{\dots},{p}_{n})$ such that ${p}_{i}=\mathrm{\mathbf{P}\mathbf{r}}[X={x}_{i}]$. Then we define the entropy of $X$ to be $H(X)={\sum}_{i=1}^{n}{p}_{i}\mathrm{log}(1/{p}_{i})$. For the special case of $n=2$, which corresponds to a Bernoulli random variable with parameter $p\in [0,1]$, we define the binary entropy to be the following function: ${H}_{2}(p)=p\mathrm{log}p(1p)\mathrm{log}(1p)$.
The entropy is a measure of randomness for a random variable. In other words, it is the number of bits of information that we get on average by observing the outcome of the random variable.
In some cases, we would like to know how much excess information we get by observing the outcome of a random variable $Y$ given that we know the outcome of another random variable $X$. This is usually called conditional entropy of $Y$ given $X$, and is defined as follows:
Let $X,Y$ be a discrete random variables supported on the sets $\mathcal{X}$ and $\mathcal{Y}$ respectively. Also let $p(x,y)$ be the joint probability mass function of $X,Y$ such that $p(x,y)=\mathrm{\mathbf{P}\mathbf{r}}[X=x,Y=y]$. Then we define the conditional entropy of $Y$ given $X$ to be:
$$H(YX)=H(X,Y)H(X)=\sum _{x\in \mathcal{X},y\in \mathcal{Y}}p(x,y)\mathrm{log}\frac{p(x,y)}{p(x)}.$$ 
Furthermore, the amount of information that is shared between two random variables is called mutual information and defined as follows: {definition} Let $X,Y$ be a discrete random variables. The mutual information between $X$ and $Y$ is defined as $I(X;Y)=H(X)H(XY)=H(X)+H(Y)H(X,Y)$. Note that this quantity is symmetric, i.e., $I(X;Y)=I(Y;X)$. We also define the conditional shared information as $I(X;YZ)=H(XZ)H(XY,Z)$.
The following well known lemma in information theory, intuitively implies that the mutual information between two random variables $X$ and $Y$ cannot be increased by transforming $Y$ into a new variable $Z$ either deterministically or by using randomness that is independent of $X$ (i.e., without using any additional knowledge for $X$).
[Data Processing Inequality] Let $X,Y,Z$ be random variables, such that $X\u27c2ZY$. Then $I(X;Z)\le I(X;Y)$. We also make use of another standard lemma known as the chain rule. {lemma}[Chain Rule] For variables $X,Y$ and $Z$ we have that $I(X;Y,Z)=I(X;Z)+I(X;YZ)$.
Finally, we use the following well known Taylor series for the binary entropy function:
Fact \thetheorem
$$1{H}_{2}\left(\frac{1}{2}+a\right)=\frac{1}{2\mathrm{ln}2}\sum _{l=1}^{\mathrm{\infty}}\frac{{(2a)}^{2l}}{l(2l1)}=O({a}^{2}).$$ 
4.2 Memory Lower Bounds for Uniformity Testing
In this section, we prove our memory lower bounds as described by the following theorem: {theorem} Let $\mathcal{A}$ be an algorithm which tests if a distribution $p$ is uniform versus $\u03f5$far from uniform with error probability $1/3$, can access the samples in a singlepass streaming fashion using $m$ bits of memory and $k$ samples, then $k\cdot m=\mathrm{\Omega}(\frac{n}{{\u03f5}^{2}})$. Furthermore, if $$ and $m\ge {k}^{2}/{n}^{0.9}$, then $k\cdot m=\mathrm{\Omega}(\frac{n\mathrm{log}n}{{\u03f5}^{4}})$. {remark} This result should hold (with worse constants) if the above bounds on $m$ and $k$ are replaced by any bounds of the form $m\ge {k}^{2}/{n}^{1c}$ and $k\le {n}^{1c}$ for any constant $c>0$.
In this rest of this section, we prove Theorem 4.2. To do so, we use the adversary method. Let $X$ be a uniformly random bit. Based on $X$, the adversary chooses the distribution $p$ on $[2n]$ bins as follows:

•
$X=0$: Pick $p={U}_{2n}$.

•
$X=1$: Pair the bins as $\{1,2\},\{3,4\},\mathrm{\dots},\{2n1,2n\}$. Now on each pair $\{2i1,2i\}$ pick a random ${Y}_{i}\in \{\pm 1\}$ to pick:
$$({p}_{2i1},{p}_{2i})=\{\begin{array}{cc}(\frac{1+\u03f5}{2n},\frac{1\u03f5}{2n}),{Y}_{i}=1\hfill & \\ (\frac{1\u03f5}{2n},\frac{1+\u03f5}{2n}),{Y}_{i}=1\hfill & \end{array}$$
In either case, we can think of the output of $p$ as being a pair $(C,V)$, where $C$ is an element of $[n]$ is chosen uniformly, and $V\in \{0,1\}$ is a fair coin if $X=0$ and has bias $\u03f5\cdot {Y}_{C}$ if $X=1$.
Let ${s}_{1},\mathrm{\dots},{s}_{k}$ be the observed samples from $p$. Let ${M}_{t}$ denote the bits stored in the memory after the algorithm sees the $t$th sample ${s}_{t}$.
Since the algorithm learns $X$ with probability $2/3$ after viewing $k$ samples, we know that $I(X;{M}_{k})>\mathrm{\Omega}(1)$. On the other hand, ${M}_{t}$ is computed from $({M}_{t1},{s}_{t})$ without using any information about $X$ ^{3}^{3} 3 Note that we can use deterministic operations and possibly random bits, which however cannot be correlated with the random variable $X$ since ${s}_{t}$ is by definition the only sample from the distribution that is drawn between the memory states ${M}_{t1}$ and ${M}_{t}$.. More formally, $X\u27c2{M}_{t}({M}_{t1},{s}_{t})$ and therefore we can use the data processing inequality (Lemma 4.1) to get:
$$I(X;{M}_{t})\le I(X;{M}_{t1},{s}_{t})=I(X;{M}_{t1})+I(X;{s}_{t}{M}_{t1}).$$ 
Our basic technique will be to bound $I(X;{s}_{t}{M}_{t1})$. This will give us an upper bound on $I(X;{M}_{k})$ via telescoping.
The sample $s$ corresponds to which pair of bins was picked and within that pair which one of two bins was picked, that is $s=(C,V)$. $V$ is a random variable taking values in $\{0,1\}$.
Since irrespective of $X$, $C$ is uniform over the pairs of bins, we note that $C$ is independent of $X$ even when conditioned on the memory $M$.
Thus,
$$I(X;{s}_{t}{M}_{t1})=I(X;{C}_{t}{V}_{t}{M}_{t1})=I(X;{V}_{t}{M}_{t1}{C}_{t}).$$ 
Let ${\alpha}_{t1}=\mathrm{\mathbf{P}\mathbf{r}}[X=1{M}_{t1}{C}_{t}]$ and thus $\mathrm{\mathbf{P}\mathbf{r}}[X=0{M}_{t1}{C}_{t}]=1{\alpha}_{t1}$.
We have that
$\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0X=0,{M}_{t1},{C}_{t}]$  $={\displaystyle \frac{1}{2}}$  
$\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0X=1,{M}_{t1},{C}_{t}]$  $={\displaystyle \frac{1+\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}$  
$\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0{M}_{t1},{C}_{t}]$  $=(1{\alpha}_{t1}){\displaystyle \frac{1}{2}}+{\alpha}_{t1}{\displaystyle \frac{1+\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}={\displaystyle \frac{1}{2}}+{\displaystyle \frac{{\alpha}_{t1}\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}.$ 
We can calculate
$I(X;{V}_{t}{M}_{t1}{C}_{t})=H({V}_{t}{M}_{t1}{C}_{t})H({V}_{t}{M}_{t1}{C}_{t}X)$  
$={H}_{2}(\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0{M}_{t1},{C}_{t}])\{\mathrm{\mathbf{P}\mathbf{r}}[X=1{M}_{t1}{C}_{t}]{H}_{2}(\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0X=1,{M}_{t1},{C}_{t}])$  
$\mathrm{\hspace{1em}}+\mathrm{\mathbf{P}\mathbf{r}}[X=0{M}_{t1}{C}_{t}]{H}_{2}(\mathrm{\mathbf{P}\mathbf{r}}[{V}_{t}=0X=0,{M}_{t1},{C}_{t}])\}$  
$={H}_{2}\left({\displaystyle \frac{1}{2}}+{\displaystyle \frac{{\alpha}_{t1}\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}\right){\alpha}_{t1}{H}_{2}\left({\displaystyle \frac{1}{2}}+{\displaystyle \frac{\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}\right)(1{\alpha}_{t1}){H}_{2}\left({\displaystyle \frac{1}{2}}\right)$  
$={\alpha}_{t1}\left[1{H}_{2}\left({\displaystyle \frac{1}{2}}+{\displaystyle \frac{\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}\right)\right]\left[1{H}_{2}\left({\displaystyle \frac{1}{2}}+{\displaystyle \frac{{\alpha}_{t1}\u03f5\mathbf{E}[{Y}_{{C}_{t}}{M}_{t1}]}{2}}\right)\right].$ 
Thus, using Fact 4.1 we have,
$I(X;{V}_{t}{M}_{t1}{C}_{t})$  $=\mathrm{\Theta}(1){\alpha}_{t1}(1{\alpha}_{t1}){\u03f5}^{2}\mathbf{E}{[{Y}_{{C}_{t}}{M}_{t1}]}^{2}$  
$\le O(1){\u03f5}^{2}\mathbf{E}{[{Y}_{{C}_{t}}{M}_{t1}]}^{2}.$ 
Since ${C}_{t}$ is uniformly random, we have that
$$I(X;{V}_{t}{M}_{t1}{C}_{t})=\frac{1}{n}\cdot \sum _{j=1}^{n}O(1){\u03f5}^{2}\mathbf{E}{[{Y}_{j}{M}_{t1}]}^{2}.$$  (5) 
We begin by proving a relatively straightforward unconditional bound on this sum using the fact that ${M}_{t1}$ has only $m$ bits of information. {lemma} We have that ${\sum}_{j=1}^{n}\mathbf{E}{[{Y}_{j}{M}_{t1}]}^{2}=O(m).$ {proof} First we notice that since $H({M}_{t1})\le m$ that $I({Y}_{1}\mathrm{\dots}{Y}_{n};{M}_{t1})\le m$, and thus that $H({Y}_{1}\mathrm{\dots}{Y}_{n}{M}_{t1})=H({Y}_{1}\mathrm{\dots}{Y}_{n})I({Y}_{1}\mathrm{\dots}{Y}_{n};{M}_{t1})\ge nm$. On the other hand, we have that
$$\sum _{i=1}^{n}H({Y}_{i}{M}_{t1})\ge H({Y}_{1}\mathrm{\dots}{Y}_{n}{M}_{t1})\ge nm.$$ 
Thus,
$$m\ge \sum _{i=1}^{n}[1H({Y}_{i}{M}_{t1})]=\mathrm{\Theta}\left(\sum _{i=1}^{n}\mathbf{E}{[{Y}_{i}{M}_{t1}]}^{2}\right),$$ 
where the equality comes from Fact 4.1 and the fact that if $\mathrm{\mathbf{P}\mathbf{r}}[{Y}_{i}=1{M}_{t1}]=\frac{1}{2}+\alpha $, then $\mathbf{E}[{Y}_{i}{M}_{t1}]=\mathrm{\mathbf{P}\mathbf{r}}[{Y}_{i}=1{M}_{t1}](+1)+\mathrm{\mathbf{P}\mathbf{r}}[{Y}_{i}=1{M}_{t1}](1)=(\frac{1}{2}+\alpha )(\frac{1}{2}\alpha )=2\alpha $. This completes our proof.
Lemma 4.2 will be enough to prove our weaker lower bound. To get the stronger one we will need a more in depth analysis. In particular, we let ${r}_{j}=\mathbf{E}[\mathrm{\#}\{1\le i\le t1:{C}_{i}=j\}{M}_{t1}]$. We first show that $\mathbf{E}[{Y}_{j}{M}_{t1}]=O(\u03f5{r}_{j})$ (see Claim 4.2 below). This leaves us with the task of bounding ${\parallel r\parallel}_{2}$. For this, we note that if $w=r/{\parallel r\parallel}_{2}$, then $r$ is only going to be large if, conditioned on ${M}_{t1}$, many of the ${C}_{i}$ will lie on components where $w$ is large. However the sum of ${w}_{{C}_{i}}$ is a sum of independent random variables, so by an appropriate Chernoff bound, we can show that it is likely not too much larger than its mean. However, since ${M}_{t1}$ only encodes $m$ bits of information, it can only correspond to an event whose likelihood is exponentially small in $m$, and this will give us our bound on ${\parallel r\parallel}_{2}$.
We will now show the following claim:
Claim \thetheorem
We have that $\mathrm{}\mathrm{E}\mathrm{[}{Y}_{j}\mathrm{}{M}_{t\mathrm{}\mathrm{1}}\mathrm{]}\mathrm{}\mathrm{=}O\mathrm{(}\u03f5\mathrm{\cdot}{r}_{j}\mathrm{)}$.
It suffices to show that
$$\mathbf{E}[{Y}_{j}{s}_{1},\mathrm{\dots},{s}_{t1},X]=O\left(\u03f5\mathrm{\#}\{1\le i\le t1:{C}_{i}=j\}\right),$$ 
as our final result will follow by averaging over the ${s}_{i}$ and $X$ conditioned on ${M}_{t1}$.
If $X=0$, this is trivial since in this case the ${s}_{i}$ convey no information about ${Y}_{j}$ so the expectation of ${Y}_{j}$ is $0$.
If $X=1$, it is not hard to see by Bayes’ Theorem that if ${n}_{1}$ is the number of times when ${s}_{i}=(j,0)$ and ${n}_{2}$ the number of times ${s}_{i}=(j,1)$, then the expectation of ${Y}_{j}$ conditioned on $X$ and the ${s}_{i}$ is
$$\frac{{(1+\u03f5)}^{{n}_{1}}{(1\u03f5)}^{{n}_{2}}{(1\u03f5)}^{{n}_{1}}{(1+\u03f5)}^{{n}_{2}}}{{(1+\u03f5)}^{{n}_{1}}{(1\u03f5)}^{{n}_{2}}+{(1\u03f5)}^{{n}_{1}}{(1+\u03f5)}^{{n}_{2}}}=O(\u03f5({n}_{1}+{n}_{2})),$$ 
and our result follows.
Since ${C}_{t}$ is uniform independent of ${M}_{t1}$, we have that
$$\mathbf{E}{[{Y}_{{C}_{t}}{M}_{t1}]}^{2}=O\left({\u03f5}^{2}\frac{1}{n}\sum _{j=1}^{n}{r}_{j}^{2}\right)=O\left(\frac{{\u03f5}^{2}{\parallel r\parallel}_{2}^{2}}{n}\right).$$ 
Therefore, we get that:
$$I(X;{V}_{t}{M}_{t1}{C}_{t})\le O(1)\frac{{\u03f5}^{4}{\parallel r\parallel}_{2}^{2}}{n}.$$  (6) 
Typical Memory States
Consider a fixed algorithm $\mathcal{A}$. Call a memory state $M$ typical for time step $t$ if the following hold:

•
$\mathrm{\mathbf{P}\mathbf{r}}({M}_{t}=M)>{e}^{m}$.

•
The corresponding vector $r$ has ${\parallel r\parallel}_{\mathrm{\infty}}\le 30$.
We will need the first condition to ensure that ${M}_{t}$ does not encode events that are too unlikely, and we will need the second to bound the maximum size of individual contributions for our Chernoff bound. Fortunately, both of these events happen with high probability as we see below:
Claim \thetheorem
Assuming $t\mathrm{\le}{n}^{\mathrm{9}\mathrm{/}\mathrm{10}}$ and $m$ is bigger than a sufficiently large multiple of $\mathrm{log}\mathit{}\mathrm{(}n\mathrm{)}$, we have that ${M}_{t}$ is typical for time $t$ with probability at least $\mathrm{1}\mathrm{}\mathrm{1}\mathrm{/}n$.
First, we deal with the probability that ${M}_{t}$ violates the first condition, in particular that it is a transcript that shows up with probability at most ${e}^{m}$. For this, we note that there are at most ${2}^{m}$ such transcripts, each occurring with probability at most ${e}^{m}$, and so the total probability that any of them occur is at most $$.
Next, we deal with the probability that ${M}_{t}$ violates the second condition. In particular, we bound the probability that there exists a $j$ so that the expected number of ${C}_{i}$ equal to $j$ for $1\le i\le t$ conditioned on ${M}_{t}$ is at least $30$. For this we, note that for any particular $j$, the expectation of $\mathrm{max}(0,\mathrm{\#}\{1\le i\le t:{C}_{i}=j\}20)$ over sets of samples is at most ${n}^{2}$. Therefore, the expectation over transcripts of $\mathrm{max}(0,{r}_{j}20)$ is at most ${n}^{2}$. Our result now follows by a Markov inequality and union bound over $j$.
We are now ready to prove an upper bound on $N={\parallel r\parallel}_{2}^{2}$ in the following lemma:
For the fixed transcript $A$ typical for time $t$, with $m\ge {t}^{2}/{n}^{0.9}$, we have
$$N={\parallel r\parallel}_{2}=O\left(\sqrt{\frac{m}{\mathrm{log}n}}\right).$$ 
Let $w=r/N$. Note that ${\parallel r\parallel}_{2}=r\cdot w$, and that ${\parallel w\parallel}_{2}=1$.
Let ${X}_{\mathrm{\ell}}={w}_{{C}_{\mathrm{\ell}}}1\le \mathrm{\ell}\le t$. These are i.i.d random variables taking values in $[0,\frac{30}{N}]$ with mean $\mathbf{E}[{X}_{\mathrm{\ell}}]=\frac{1}{n}\sum _{i=1}^{n}{w}_{i}\le \frac{1}{\sqrt{n}}$, since ${\parallel w\parallel}_{2}=1$.
Define $X:=\sum _{\mathrm{\ell}=1}^{t}{w}_{{C}_{\mathrm{\ell}}}$ and note that $\mu =\mathbf{E}[X]\le \frac{t}{\sqrt{n}}$. We have that
$N$  $=\mathbf{E}[{\displaystyle \sum _{\mathrm{\ell}=1}^{t}}{w}_{{C}_{\mathrm{\ell}}}{M}_{t}=A]={\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}({M}_{t}=A)}}{\displaystyle \underset{a=0}{\overset{\mathrm{\infty}}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a,{M}_{t}=A]da$  
$={\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]}}{\displaystyle \underset{a=0}{\overset{N/2}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a,{M}_{t}=A]da+{\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]}}{\displaystyle \underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a,{M}_{t}=A]da$  
$\le {\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]}}{\displaystyle \underset{a=0}{\overset{N/2}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]da+{\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]}}{\displaystyle \underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a]da$  
$={\displaystyle \frac{N}{2}}+{\displaystyle \frac{1}{\mathrm{\mathbf{P}\mathbf{r}}[{M}_{t}=A]}}{\displaystyle \underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a]da.$ 
Thus, we have
$$\frac{N}{2}\le {e}^{m}\underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}\mathrm{\mathbf{P}\mathbf{r}}[X>a]da.$$ 
Now let us bound the tail $\mathrm{\mathbf{P}\mathbf{r}}[X>a]$. We have $\mathrm{\mathbf{P}\mathbf{r}}[X>a]=\mathrm{\mathbf{P}\mathbf{r}}[Nx>Na]$. We would like to show that $N\le \sqrt{\frac{m}{\mathrm{log}n}}$. Thus, we can assume that $N>4\frac{t}{{n}^{0.49}}$ else we already have $N\le \sqrt{\frac{m}{\mathrm{log}n}}$. Hence, we can assume that $a>2\frac{t}{{n}^{0.49}}$ in the above integral. We write $a=(1+\delta )\mu $ and apply the Chernoff bound on the random variable $\frac{N}{30}\cdot X$ (note that this is a sum of i.i.d random variables supported in $[0,1]$) to get:
$$ 
We have $1+\delta =\frac{a}{\mu}>\frac{N\sqrt{n}}{30t}>{n}^{1/200}$. Thus, for $a\ge \frac{N}{2}$ we have
$$\mathrm{Pr}(X>a)\le {e}^{\alpha Na\mathrm{log}n},$$ 
for some constant $\alpha >0$. Substituting in the above integral gives:
$\frac{N}{2}$  $\le {e}^{m}{\displaystyle \underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}}\mathrm{\mathbf{P}\mathbf{r}}[X>a]da\le {e}^{m}{\displaystyle \underset{a=N/2}{\overset{\mathrm{\infty}}{\int}}}{e}^{\alpha Na\mathrm{log}n}da={\displaystyle \frac{1}{\alpha N\mathrm{log}n}}{e}^{m\alpha {N}^{2}\mathrm{log}n/2}.$ 
Thus, we have for some constant $\alpha $:
$$\frac{\alpha {N}^{2}\mathrm{log}n}{2}\le {e}^{m\alpha {N}^{2}\mathrm{log}n/2}.$$ 
Since $m\ge 1$, the equation $\theta \le {e}^{m\theta}$ can have a solution only when $\theta \le m$. That is $\frac{\alpha {N}^{2}\mathrm{log}n}{2}\le m$, this gives us the required bound ${\parallel r\parallel}_{2}=N\le \sqrt{2/\alpha}\sqrt{\frac{m}{\mathrm{log}n}}=O(\sqrt{\frac{m}{\mathrm{log}n}})$.
[Proof of Theorem 4.2] Using Equation (5) and Lemma 4.2, we get that
$$I(X;{V}_{t}{M}_{t1}{C}_{t})\le O(1)\frac{{\u03f5}^{2}m}{n}.$$ 
However, we know that:
$\mathrm{\Omega}(1)\le I({M}_{k};X)$  $={\displaystyle \sum _{t=0}^{k1}}I({M}_{t+1};X)I({M}_{t};X)$  
$={\displaystyle \sum _{t=0}^{k1}}I({M}_{t},{S}_{t+1};X)I({M}_{t};X)$  
$={\displaystyle \sum _{t=0}^{k1}}I({S}_{t+1};X{M}_{t})$  
$={\displaystyle \sum _{t=0}^{k1}}I({V}_{t+1};X{M}_{t},{C}_{t+1})$  
$=O(1){\displaystyle \frac{k{\u03f5}^{2}m}{n}}.$ 
This implies that $k\cdot m=\mathrm{\Omega}(\frac{n}{{\u03f5}^{2}})$.
Under our stronger assumptions, we can instead use Lemma 4.2 to similarly obtain:
$\mathrm{\Omega}(1)\le I({M}_{k};X)$  $={\displaystyle \sum _{t=0}^{k1}}I({V}_{t+1};X{M}_{t},{C}_{t+1})$  
$=O(1){\displaystyle \frac{k{\u03f5}^{4}m}{n\mathrm{log}n}}+O(k/n).$ 
The last line here comes from the fact that $I({V}_{t+1};X{M}_{t},{C}_{t+1})=O({\u03f5}^{4}m/n\mathrm{log}(n))$ for typical transcripts ${M}_{t}$ and the fact that ${M}_{t}$ is typical except with probability $1/n$.
Thus, equivalently, we have $k\cdot m=\mathrm{\Omega}(\frac{n\mathrm{log}n}{{\u03f5}^{4}})$, completing the proof.
4.3 Communication Lower Bounds for Uniformity Testing
In this section, we will show a communication lower bound for distributed uniformity testing algorithms in our onepass communication model, via a reduction to the streaming/limited memory setting. In particular, we show the following theorem:
Suppose that there exists a communication protocol with a transcript of length $T$ bits, for the setting where each machine holds $\mathrm{\ell}$ samples, that can distinguish between a uniform distribution and one that is $\u03f5$far from uniform in total variation distance. Then there exists a streaming algorithm that uses at most $m=T+\mathrm{\ell}\cdot \mathrm{log}n$ bits of memory and has access to a stream of at most $s=T\cdot \mathrm{\ell}$ samples.
We will simulate the protocol by storing in memory the entire communication transcript up to any given point in the simulated protocol, while having some additional space in order to temporarily store the samples of a single player (machine) at a time.
In particular, we consider the stream of $t\cdot \mathrm{\ell}$ samples, where $t$ is the number of players that participate, that is created by taking the $\mathrm{\ell}$ samples of the first player to speak and iteratively appending the $\mathrm{\ell}$ samples of the next player to speak until there are no more players. We also use the memory to remember the communication transcript so far at any given point and the samples of the player speaking in that round so that the algorithm is able to compute the bits that the players send.
Therefore, during any given round $i$ of the communication protocol, the partial transcript ${T}_{i1}$ of the communication in the first $i1$ rounds is stored in memory along with the $\mathrm{\ell}$ samples of the player that is about to speak in round $i$. Note that, since the referee is not going to ask any questions again to that particular player, the exact samples of that player are no longer useful to the algorithm after the current round ends. Therefore, those $\mathrm{\ell}\mathrm{log}n$ bits of additional memory can be reused while simulating the next round. However, the algorithm will use the bits transmitted by that player along with the current partial transcript ${T}_{i1}$, to create the new partial transcript ${T}_{i}$.
Observe that every player has to send at least $1$ bit, since otherwise we can assume that they did not participate in the protocol. Therefore, we have that $t\le T$ and consequently our stream will have at most $s=T\cdot \mathrm{\ell}$ samples.
Furthermore, the transcript that is created after the last player speaks is the one that contains the most information among the partial transcripts which are all optimally compressed. Thus, we have that $\forall i:{T}_{i}\le T$, where $T={T}_{t}$ is the transcript of the entire communication. This means that no more than $m=T+\mathrm{\ell}\cdot \mathrm{log}n$ bits of memory are needed at any given point of the execution.
Using the above theorem, we can prove the following two corollaries:
Let $\pi $ be a distributed communication protocol, for the setting where each machine holds $\mathrm{\ell}$ samples, which tests if a distribution $p$ is uniform versus $\u03f5$far from uniform with error probability $1/3$, and the referee asks questions to each player only once. Then, $\pi $ must involve $\mathrm{\Omega}\left(\frac{\sqrt{n/\mathrm{\ell}}}{\u03f5}\right)$ bits of communication for any $\mathrm{\ell}=O\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}{(\mathrm{log}n)}^{1/3}}\right)$. Furthermore, $\pi $ must involve $\mathrm{\Omega}\left(\frac{\sqrt{n/\mathrm{\ell}}}{{\u03f5}^{2}}\sqrt{\mathrm{log}n}\right)$ bits of communication for any $\mathrm{\ell}=O\left({\u03f5}^{4/3}{n}^{0.3}\right)$. {proof} Suppose, for the sake of contradiction, that there exists such a protocol that uses $t=\mathrm{\Theta}\left(\frac{\sqrt{n/\mathrm{\ell}}}{{\u03f5}^{2}}\sqrt{\mathrm{log}n}\right)$ bits of communication with a sufficiently small implied constant. Then, using theorem 4.3, we conclude that there also exists an streaming algorithm that uses a stream of size $s\le t\mathrm{\ell}$ samples and a memory of size $m=\mathrm{\Theta}(t+\mathrm{\ell}\mathrm{log}(n))=\mathrm{\Theta}(t)$ bits. Furthermore, we have that
$${s}^{2}/(m{n}^{0.99})=\mathrm{\Theta}(t{\mathrm{\ell}}^{2}/{n}^{0.99})\ll ({\mathrm{\ell}}^{3/2}/({n}^{0.45}{\u03f5}^{2}))\ll 1.$$ 
Therefore, Theorem 4.2 applies and we must have $ms=\mathrm{\Omega}(n\mathrm{log}(n)/{\u03f5}^{4})$, but $ms=O({t}^{2}\mathrm{\ell})$, which is a sufficiently small multiple of $n\mathrm{log}(n)/{\u03f5}^{4}$, that it yields a contradiction.
Note that for any $\mathrm{\ell}=O\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}{(\mathrm{log}n)}^{1/3}}\right)$, it still holds that $m=\mathrm{\Theta}(t+\mathrm{\ell}\mathrm{log}(n))=\mathrm{\Theta}(t)$. We will combine now Theorem 4.3 with the weaker version of Theorem 4.2, and assume that there exists such a protocol that uses ${t}^{\prime}=\mathrm{\Theta}\left(\frac{\sqrt{n/\mathrm{\ell}}}{\u03f5}\right)$ bits of communication with a sufficiently small implied constant. In this case, we must have $ms=\mathrm{\Omega}(n/{\u03f5}^{2})$, but $ms=O({({t}^{\prime})}^{2}\mathrm{\ell})$, which is a sufficiently small multiple of $n/{\u03f5}^{2}$, that it yields a contradiction.
Furthermore, if we have a restricted number of samples, we can get better communication lower bounds: {corollary} Let $\pi $ be a distributed communication protocol, for the setting where each machine holds $\mathrm{\ell}$ samples with a total of $t$ machines, which tests if a distribution $p$ is uniform versus $\u03f5$far from uniform with error probability $1/3$, and the referee asks questions to each player only once. Then, if $t=O\left(\frac{\sqrt{n/\mathrm{\ell}}}{{\u03f5}^{2}}\sqrt{\mathrm{log}n}\right)$ and $t\mathrm{\ell}=O({n}^{0.6}/{\u03f5}^{4/3})$, $\pi $ must involve $\mathrm{\Omega}(\frac{n\mathrm{log}(n)}{{\u03f5}^{4}t\mathrm{\ell}})$ bits of communication. {proof} Again we use Theorem 4.3. We now have a streaming algorithm using $k=t\mathrm{\ell}$ samples and $m=\pi +\mathrm{\ell}\mathrm{log}(n)$ memory. We claim that this is impossible even if $\pi =p=\mathrm{\Theta}(\frac{n\mathrm{log}(n)}{{\u03f5}^{4}t\mathrm{\ell}})$ with the implied constant sufficiently small. In fact, this in case we have that $m=O(p)$. We have that $m{n}^{0.9}k=\mathrm{\Theta}({n}^{1.9}\mathrm{log}(n)/{\u03f5}^{4})>{k}^{3}$, and so the strong version of Theorem 4.2 applies. This means that $mk=\mathrm{\Omega}(n\mathrm{log}(n)/{\u03f5}^{4})$, when in reality it is too small a constant times this, yielding a contradiction.
A case of particular interest for the above is when $t\mathrm{\ell}=O(\sqrt{n}/{\u03f5}^{2})$ is the informationtheoretically optimal number of samples. In this case (so long as $\mathrm{\ell}=O(\mathrm{log}(n))$) our communication must be at least $\mathrm{\Omega}(\sqrt{n}\mathrm{log}(n)/{\u03f5}^{2})$, which is not much better than sending all of the samples directly.
Finally, the following corollary gives a communication complexity lower bound for all values of $\mathrm{\Omega}\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}{(\mathrm{log}n)}^{1/3}}\right)\le \mathrm{\ell}\le O\left(\frac{\sqrt{n}}{{\u03f5}^{2}}\right)$ using the weaker version of Theorem 4.2. {corollary} Let $\pi $ be a distributed communication protocol, for the setting where each machine holds $\mathrm{\ell}$ samples, which tests if a distribution $p$ is uniform versus $\u03f5$far from uniform with error probability $1/3$, and the referee asks questions to each player only once. Then, $\pi $ must involve $\mathrm{\Omega}(\frac{n}{{\mathrm{\ell}}^{2}{\u03f5}^{2}\mathrm{log}n})$ bits of communication for any $\mathrm{\Omega}\left(\frac{{n}^{1/3}}{{\u03f5}^{4/3}{(\mathrm{log}n)}^{1/3}}\right)\le \mathrm{\ell}\le O\left(\frac{\sqrt{n}}{{\u03f5}^{2}}\right)$. {proof} Suppose, for the sake of contradiction, that there exists such a protocol that uses $t=\mathrm{\Theta}\left(\frac{n}{{\mathrm{\ell}}^{2}{\u03f5}^{2}\mathrm{log}n}\right)$ bits of communication with a sufficiently small implied constant. Then, using Theorem 4.3, we conclude that there also exists an streaming algorithm that uses a stream of size $s$ samples and a memory of size $m$ bits, such that $m\cdot k=\mathrm{\Theta}(t{\mathrm{\ell}}^{2}\mathrm{log}n)$, since $k=t\mathrm{\ell}$ and $m=\mathrm{\Theta}(\mathrm{\ell}\mathrm{log}n)$ for this range of values for $\mathrm{\ell}$.
This means that $mk=\mathrm{\Omega}(t{\mathrm{\ell}}^{2}\mathrm{log}n)=\mathrm{\Omega}(\frac{n}{{\u03f5}^{2}})$, when in reality it is too small a constant times this, yielding a contradiction due to Theorem 4.2.
5 Communication and Memory Efficient Closeness Testing
In this section, we design our protocols for closeness testing. We start with the setting of memory and then give our communication efficient protocols.
5.1 Memory Efficient Closeness Testing
In this section, we provide an algorithm for closeness testing in the streaming model that uses $O\left(\frac{n}{\sqrt{m}{\u03f5}^{2}}\right)$ samples and $O(m\mathrm{log}(n))$ bits of memory where $m$ is a parameter such that
$$\mathrm{min}(n,{n}^{2/3}/{\u03f5}^{4/3})\gg m\gg 1.$$ 
By reparametrizing, this implies an algorithm with $\mathrm{min}(n\mathrm{log}(n),{n}^{2/3}\mathrm{log}(n)/{\u03f5}^{4/3})\gg m\gg \mathrm{log}(n)$ bits of memory and $O\left(\frac{n\sqrt{\mathrm{log}(n)}}{\sqrt{m}{\u03f5}^{2}}\right)$ samples. However, we are going to use the former parametrization assuming an upper bound of $O(m)$ words of memory (each of length $O(\mathrm{log}n)$ bits), as it will be more convenient for us, so we will use that.
The performance of the algorithm is described in the following theorem: {theorem} Let $p,q$ be two discrete distributions on $[n]$. Suppose that $\mathrm{min}(n,{n}^{2/3}/{\u03f5}^{4/3})\gg m\gg 1$. Then there exists a single pass streaming algorithm that uses at most $m\mathrm{log}n$ bits of memory and $O(\frac{n}{\sqrt{m}{\u03f5}^{2}})$ samples from $p$ and $q$, and distinguishes between the cases that $p=q$ versus ${\parallel pq\parallel}_{1}\ge \u03f5$ with probability at least $2/3$.
The algorithm is given in pseudocode below:
Algorithm TestClosenessMemory$\mathrm{(}p\mathrm{,}q\mathrm{,}n\mathrm{,}m\mathrm{,}\u03f5\mathrm{)}$ Input: Sample access to distributions $p,q$ over $[n]$, memory bound $m$, and $\u03f5>0$. Output: “YES” if $p=q$; “NO” if ${\parallel pq\parallel}_{1}\ge \u03f5.$ 1. Draw $O(m)$ samples from $p$ and $q$ to flatten them to ${p}^{\prime},{q}^{\prime}$ such that ${\parallel {p}^{\prime}\parallel}_{2},{\parallel {q}^{\prime}\parallel}_{2}\le O\left(\frac{1}{\sqrt{m}}\right)$. Let $[{n}^{\prime}]$ be the new domain. 2. Apply a hash map $h$ to ${p}^{\prime},{q}^{\prime}$. This hash map $h:[n]\to [m]$ approximately preserves ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}$ and ${\parallel {p}^{\prime}\parallel}_{2}$ with constant probability. 3. Use a standard ${\mathrm{\ell}}_{2}$ tester to distinguish between $h({p}^{\prime})=h({q}^{\prime})$ and ${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}\gg \frac{\u03f5}{\sqrt{n}}$.
This section is devoted to the proof of Theorem 5.1.
Flatten $p,$ and $q$.
Our algorithm begins by taking (and storing) $m$ samples from each of $p$ and $q$. We use these samples to produce the split distributions ${p}^{\prime}$ and ${q}^{\prime}$ whereby the ${i}^{\text{th}}$ bin is split into ${a}_{i}$ equal subbins where ${a}_{i}$ is one more than the number of copies of $i$ in this set of samples. We note the following important facts from [Diakonikolas and Kane(2016)]:

•
Given the list of samples, one can simulate a sample from ${p}^{\prime}$ (resp. ${q}^{\prime}$) from a single sample of $p$ (resp. $q$) and some additional randomness.

•
${\parallel pq\parallel}_{1}={\parallel {p}^{\prime}{q}^{\prime}\parallel}_{1}$.

•
${\parallel {p}^{\prime}\parallel}_{2},{\parallel {q}^{\prime}\parallel}_{2}=O(1/\sqrt{m})$ with at least $9/10$ probability.
Our analysis from here on out will be under the assumption that the last property holds.
Hash ${p}^{\prime}$ and ${q}^{\prime}$.
Our next step is to pick a hash map $h:[{n}^{\prime}]\to [m]$ (where ${n}^{\prime}$ is the size of the domain of ${p}^{\prime}$ and ${q}^{\prime}$) from a $4$wise independent family (note that for an appropriate family we can store $h$ using $O(m\mathrm{log}(n))$ bits). We claim that with at least $9/10$ probability that ${\parallel h({p}^{\prime})\parallel}_{2},{\parallel h({q}^{\prime})\parallel}_{2}$ are not too big and that ${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}\approx {\parallel h(p)h(q)\parallel}_{2}$.
In particular, we show the following lemma: {lemma} We have the following:
${\mathbf{E}}_{h}[{\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}]$  $=\left(1{\displaystyle \frac{1}{m}}\right){\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}$  
${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{h}\left[{\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}\right]$  $={\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right)\left[{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{4}{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{4}^{4}\right]$  
${\mathbf{E}}_{h}[{\parallel h({p}^{\prime})\parallel}_{2}^{2}]$  $={\displaystyle \frac{1}{m}}+\left(1{\displaystyle \frac{1}{m}}\right){\parallel {p}^{\prime}\parallel}_{2}^{2}$  
${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{h}\left[{\parallel h({p}^{\prime})\parallel}_{2}^{2}\right]$  $={\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right)\left[{\parallel {p}^{\prime}\parallel}_{2}^{4}{\parallel {p}^{\prime}\parallel}_{4}^{4}\right]$ 
We can write:
${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}$  $={\displaystyle \sum _{i\in [m]}}{\left[{\displaystyle \sum _{j\in [{n}^{\prime}]}}({p}_{j}^{\prime}{q}_{j}^{\prime})I\{h(j)=i\}\right]}^{2}$  
$={\displaystyle \sum _{i\in [m]}}{\displaystyle \sum _{{j}_{1},{j}_{2}\in [{n}^{\prime}]}}({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})I\{h({j}_{1})=h({j}_{2})=i\}$  
$={\displaystyle \sum _{{j}_{1},{j}_{2}\in [{n}^{\prime}]}}({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})I\{h({j}_{1})=h({j}_{2})\}$  
$=\parallel {p}^{\prime}{q}^{\prime}{\parallel}_{2}^{2}+{\displaystyle \sum _{{j}_{1}\ne {j}_{2}\in [{n}^{\prime}]}}({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})I\{h({j}_{1})=h({j}_{2})\}.$ 
We therefore have that:
${\mathbf{E}}_{h}[{\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}]$  $={\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}+{\displaystyle \frac{1}{m}}{\displaystyle \sum _{{j}_{1}\ne {j}_{2}\in [{n}^{\prime}]}}({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})$  
$={\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}+{\displaystyle \frac{1}{m}}{\displaystyle \sum _{{j}_{1}\in [{n}^{\prime}]}}\left[({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime}){\displaystyle \sum _{{j}_{2}\ne {j}_{1}\in [{n}^{\prime}]}}({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})\right]$  
$={\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}{\displaystyle \frac{1}{m}}{\displaystyle \sum _{j\in [{n}^{\prime}]}}{({p}_{j}^{\prime}{q}_{j}^{\prime})}^{2}=\left(1{\displaystyle \frac{1}{m}}\right){\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2},$ 
and
${\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{h}[{\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}]$  $={\displaystyle \sum _{{j}_{1}\ne {j}_{2}\in [{n}^{\prime}]}}{\mathrm{\mathbf{V}\mathbf{a}\mathbf{r}}}_{h}\left[({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})I\{h({j}_{1})=h({j}_{2})\}\right]$  
$={\displaystyle \sum _{{j}_{1}\ne {j}_{2}\in [{n}^{\prime}]}}{({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})}^{2}{({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})}^{2}{\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right)$  
$={\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right){\displaystyle \sum _{{j}_{1}\in [{n}^{\prime}]}}{({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})}^{2}\left[{\displaystyle \sum _{{j}_{2}\ne {j}_{1}\in [{n}^{\prime}]}}{({p}_{{j}_{2}}^{\prime}{q}_{{j}_{2}}^{\prime})}^{2}\right]$  
$={\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right){\displaystyle \sum _{{j}_{1}\in [{n}^{\prime}]}}{({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})}^{2}\left[{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}{({p}_{{j}_{1}}^{\prime}{q}_{{j}_{1}}^{\prime})}^{2}\right]$  
$={\displaystyle \frac{1}{m}}\left(1{\displaystyle \frac{1}{m}}\right)\left[{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{4}{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{4}^{4}\right].$ 
The other two identities follow similarly.
By Chebyshev’s inequality, we have that the following statements hold true with $90\%$ probability:
${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}^{2}$  $\ge {\displaystyle \frac{1}{2}}{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}$  
${\parallel h({p}^{\prime})\parallel}_{2}^{2}$  $\le {\displaystyle \frac{1}{m}}+{\displaystyle \frac{3}{2}}{\parallel {p}^{\prime}\parallel}_{2}^{2}=O(1/m).$ 
We now have to distinguish between a completeness case where $p=q$ and thus $h({p}^{\prime})=h({q}^{\prime})$ and a soundness case where ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{1}={\parallel pq\parallel}_{1}\ge \u03f5$, and therefore ${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}\gg {\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}\gg \frac{\u03f5}{\sqrt{n}}$.
We will also need the following lemma from [Chan et al.(2014)Chan, Diakonikolas, Valiant, and Valiant]: {lemma} Let $p,q$ be distributions such that $\mathrm{max}({\parallel p\parallel}_{2},{\parallel q\parallel}_{2})\le b$, then there is an estimator that takes $O(\frac{b}{{\u03f5}^{2}})$ samples from $p,q$ and estimates ${\parallel pq\parallel}_{2}$ up to an error of $\u03f5$.
[Proof of Theorem 5.1] Using the tester from Lemma 5.1 for ${\u03f5}^{\prime}=\frac{\u03f5}{\sqrt{n}}$ and given that $b=1/\sqrt{m}$, we can distinguish between $h({p}^{\prime})=h({q}^{\prime})$ and ${\parallel h({p}^{\prime})h({q}^{\prime})\parallel}_{2}\gg \frac{\u03f5}{\sqrt{n}}$ in $O\left(\frac{n}{\sqrt{m}{\u03f5}^{2}}\right)$ samples from $h({p}^{\prime})$ and $h({q}^{\prime})$ (which can be simulated given samples from $p$ and $q$). We note also that this tester only needs to know the number of samples from each of $h({p}^{\prime})$ and $h({q}^{\prime})$ that landed in each bin, and can thus be simulated in a streaming algorithm with $O(m\mathrm{log}(n))$ memory by keeping a running total of the number of samples from each bin. This establishes the correctness of our algorithm.
As far as memory usage is concerned, the algorithm uses a total of $O(m\mathrm{log}(n))$ bits of memory for each of its steps. In particular, these steps are: recording a set of samples for flattening, storing the seed of the hash function $h$, and storing the counts of the number of samples from $h({p}^{\prime}),h({q}^{\prime})$ from each bin. Thus, the total memory usage is $O(m\mathrm{log}(n))$ bits.
5.2 Communication Efficient Algorithm for Distributed Closeness Testing
We use a somewhat different algorithm for the communication version of this problem. The basic idea is that while our memory algorithm compared $h(p)$ to $h(q)$ for some hash function $h$, our algorithm here will compare the conditional distribution $(pW)$ to $(qW)$, for some randomly chosen subset $W$ of our domain. After applying some flattening, we can ensure that with high probability the difference between $p$ and $q$ on $W$ approximates the difference of $p$ and $q$ on the whole domain. Since $W$ is small, we will need fewer samples to test closeness on $W$. Of course, we cannot make $W$ too small, as then we will need to query too many machines before even finding a sample from $W$. This is balanced our when $W\approx n/(\mathrm{\ell}\mathrm{log}(n))$, so that one out of every $\mathrm{log}(n)$ machines should have a sample (which it communicates in $\mathrm{log}(n)$ bits), while the other $\mathrm{log}(n)$ machines need one sample each to tell us that they have no samples from $W$.
Suppose that $\mathrm{\ell}=O(n{\u03f5}^{4}/\mathrm{log}(n))$. Then there exists an algorithm that given distributed sample access to two distributions $p$ and $q$ over $[n]$ distinguishes with probability $2/3$ between the cases $p=q$ and ${\parallel pq\parallel}_{1}>\u03f5$ using $O\left(\frac{{n}^{2/3}{\mathrm{log}}^{1/3}(n)}{{\mathrm{\ell}}^{2/3}{\u03f5}^{4/3}}\right)$ bits of communication.
The algorithm is given in pseudocode below:
Algorithm TestClosenessDistributed$\mathrm{(}p\mathrm{,}q\mathrm{,}n\mathrm{,}\u03f5\mathrm{)}$ Input: Each player has $\mathrm{\ell}$ samples from each of $p$ and $q$ over $[n]$, $\u03f5>0$. Output: “YES” if $p=q$; “NO” if ${\parallel pq\parallel}_{1}\ge \u03f5.$ 1. Let $C$ be a sufficiently large constant. Abort the following algorithm if more than $\frac{{C}^{2}{(n\mathrm{log}n)}^{2/3}}{{\mathrm{\ell}}^{2/3}{\u03f5}^{4/3}}$ bits of communication are ever used. 2. Draw $N=\frac{C\mathrm{\ell}(\mathrm{log}n)}{\u03f5}$ samples from $p$ and $q$ to flatten them to ${p}^{\prime}$ and ${q}^{\prime}$. Let $[{n}^{\prime}]$ be the new domain. 3. The referee picks a random subset $W$ of $[{n}^{\prime}]$ by selecting each element with probability $r=\frac{1}{\mathrm{\ell}\mathrm{log}n}$ and broadcasts this set $W$ to all the machines. 4. The referee asks $M=C\mathrm{log}(n){W}^{2/3}/{\u03f5}^{4/3}$ machines first if they have any samples from $W$, and if so for the list of these samples along with which distribution they are from. 5. Let ${m}_{1}$ of the above samples be from $p$ and ${m}_{2}$ be from $q$. Unless $$ and ${m}_{1}>W{C}^{2/3}/{\u03f5}^{4/3}$ return “NO”. 6. Use the above samples to test $\u03f5/{C}^{1/2}$closeness of two distributions on $W$ and return the result.
This section is devoted to the proof of Theorem 5.2.
Using the same analysis for flattening as in [Diakonikolas and Kane(2016)] (see also Section 5.1) gives us that ${p}^{\prime},{q}^{\prime}$ satisfy ${\parallel {p}^{\prime}\parallel}_{2},{\parallel {q}^{\prime}\parallel}_{2}\le \frac{1}{\sqrt{N}}$ and that ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{1}={\parallel pq\parallel}_{1}$ with probability at least $99\%$. Note that ${p}_{W}^{\prime},{q}_{W}^{\prime}$ are nonnormalized pseudodistributions given by restrictions of ${p}^{\prime},{q}^{\prime}$ to $W$, and $({p}^{\prime}W)$ and $({q}^{\prime}W)$ (the corresponding conditional distributions) are their normalized distributions.
We also note that
$\mathbf{E}[{\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}]$  $={\displaystyle \sum _{i}}{{p}_{i}{q}_{i}}^{2}\mathbf{E}[1/({a}_{i}+1)]$  
$=O\left({\displaystyle \sum _{i}}{{p}_{i}{q}_{i}}^{2}/(N({p}_{i}+{q}_{i}))\right)=O(1/N){\displaystyle \sum _{i}}{p}_{i}{q}_{i}=O({\parallel pq\parallel}_{1}/N).$ 
Therefore, ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}=O({\parallel pq\parallel}_{1}/N)$ with $99\%$ probability. We assume this and the above bounds on ${\parallel {p}^{\prime}\parallel}_{2}$ and ${\parallel {q}^{\prime}\parallel}_{2}$ throughout the rest.
Next, we analyze the sizes of $W,p(W),q(W)$ and ${\parallel p}_{W}{{q}_{W}\parallel}_{1}$. In particular, we note that since $W$ selects each element independently with probability $1/(\mathrm{\ell}\mathrm{log}(n))$, $W$ has mean ${n}^{\prime}/(\mathrm{\ell}\mathrm{log}(n))$ with a similar variance, and so $W=\mathrm{\Theta}(n/(\mathrm{\ell}\mathrm{log}(n)))$ with $99\%$ probability (note that ${n}^{\prime}=n+N=\mathrm{\Theta}(n)$). The mean of ${p}^{\prime}(W)=1/(\mathrm{\ell}\mathrm{log}(n))$ and the variance is ${\parallel {p}^{\prime}\parallel}_{2}^{2}r$, therefore with $99\%$ probability ${p}^{\prime}(W)=\mathrm{\Theta}(nr),$ and similarly for ${q}^{\prime}(W)$. Finally, we have that ${\parallel {p}^{\prime}}_{W}{{q}_{W}\parallel}_{1}$ has mean ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{1}r={\parallel pq\parallel}_{1}r$ and variance ${\parallel {p}^{\prime}{q}^{\prime}\parallel}_{2}^{2}r=O({\parallel pq\parallel}_{1}r/N)$. So by Chebyshev’s inequality, with $99\%$ probability we have that if either $p=q$ or ${\parallel pq\parallel}_{1}\ge \u03f5$, then ${\parallel {p}^{\prime}}_{W}{{{q}^{\prime}}_{W}\parallel}_{1}=\mathrm{\Theta}({\parallel pq\parallel}_{1}r).$
We next consider the completeness and soundness cases, ignoring the possibility of the early abort.
Completeness
If $p=q$, then ${p}^{\prime}(W)={q}^{\prime}(W)$ and $(pW)=(qW)$. We note that ${m}_{1}$ and ${m}_{2}$ each have average values ${p}^{\prime}(W)M\mathrm{\ell}=\mathrm{\Theta}(r\mathrm{\ell}M)=\mathrm{\Theta}(M/\mathrm{log}(n))$ and variances less than their means. This implies that with at least $99\%$ probability it holds $$ and ${m}_{1}>W{C}^{2/3}/{\u03f5}^{4/3}$. Additionally, since $({p}^{\prime}W)=({q}^{\prime}W)$, we will pass the closeness test for these distributions.
Soundness
If ${\parallel pq\parallel}_{1}>\u03f5$, we have that ${\parallel {p}^{\prime}}_{W}{{{q}^{\prime}}_{W}\parallel}_{1}=\mathrm{\Omega}(\u03f5r).$ We note that this implies that either ${p}^{\prime}(W){q}^{\prime}(W)>\u03f5r/{C}^{1/3}$ or $\parallel ({p}^{\prime}W)({q}^{\prime}W){\parallel}_{1}>\u03f5/{C}^{1/2}$. This is because
${\parallel {p}^{\prime}}_{W}{{{q}^{\prime}}_{W}\parallel}_{1}$  $=\parallel ({p}^{\prime}W)p(W)({q}^{\prime}W)q(W){\parallel}_{1}$  
$\le \parallel ({p}^{\prime}W)p(W)({q}^{\prime}W)p(W){\parallel}_{1}+\parallel ({q}^{\prime}W)p(W)({q}^{\prime}W)q(W){\parallel}_{1}$  
$=p(W)\parallel ({p}^{\prime}W)({q}^{\prime}W){\parallel}_{1}+{p}^{\prime}(W){q}^{\prime}(W).$ 
First, consider what happens if ${p}^{\prime}(W){q}^{\prime}(W)>\u03f5r/{C}^{1/3}$. We notice that ${m}_{1}$ and ${m}_{2}$ have means of $M\mathrm{\ell}{p}^{\prime}(W)=\mathrm{\Theta}(M/\mathrm{log}(n))$ and $M\mathrm{\ell}{q}^{\prime}(W)=\mathrm{\Theta}(M/\mathrm{log}(n))$, respectively, with variances on the order of their means. Now if ${p}^{\prime}(W){q}^{\prime}(W)>\u03f5r/{C}^{1/3}$, the means of ${m}_{1}$ and ${m}_{2}$ will differ by $\mathrm{\Omega}(M\u03f5/\mathrm{log}(n){C}^{1/3})=\mathrm{\Omega}({C}^{2/3}{n}^{2/3}/({\mathrm{\ell}}^{2/3}{\u03f5}^{1/3}))$, while the variance is $O(C{n}^{2/3}/({\mathrm{\ell}}^{2/3}{\u03f5}^{4/3})).$ Since the difference of the means is much bigger than both the square root of the mean of ${m}_{1}$ and the square root of the variance, ${m}_{1}{m}_{2}$ will be bigger than $C\sqrt{{m}_{1}}$ with $99\%$ probability.
On the other hand. if $\parallel ({p}^{\prime}W)({q}^{\prime}W){\parallel}_{1}>\u03f5/{C}^{1/2}$, our closeness tester in the last step will fail.
Communication Complexity
Here we show that the communication complexity of the algorithm is within the desired bounds, and that we have enough samples to perform the test in the last step. Firstly, we note that the $N$ samples in the first step requires only $N\mathrm{log}(n)$ communication, which is well within our bounds. The other major step requires asking $M$ machines. It takes only $O(M)$ communication for each machine to report whether or not they have a sample, and we have an average of $M\mathrm{\ell}({p}^{\prime}(W)+{q}^{\prime}(W))$ samples that take $O(\mathrm{log}(n))$ bits each. This is at most $O(M\mathrm{\ell}\mathrm{log}(n)r)=O(C{W}^{2/3}/{\u03f5}^{4/3})=O(C{n}^{2/3}/({\mathrm{\ell}}^{2/3}{\mathrm{log}}^{2/3}(n){\u03f5}^{4/3}))$ samples, for an appropriate number of bits.
Finally, we note that for the last step since $W=n/(\mathrm{\ell}\mathrm{log}(n))\gg {\u03f5}^{4}$, our tester only requires $O({W}^{2/3}/{\u03f5}^{4/3})$ samples, which are available. This completes the proof of Theorem 5.2.
6 Conclusions and Future Directions
This work gave algorithms and lower bounds, in some cases matching, for distribution testing with communication and memory constraints. Our work is a first step in these directions and suggests a host of interesting open problems. More concretely:
Communication Lower Bounds without Onepass Assumption
Our current techniques for proving communication lower bounds seem to depend fairly strongly on the onepass assumption. In particular, when bounding the information learned by the ${t}^{\text{th}}$ sample, it is critical for us to know that the information that we have from the current transcript is independent of that sample. Unfortunately, it is not clear how to get around that obstacle, and without it we have only the trivial lower bound of $\mathrm{\Omega}(\sqrt{n}/({\u03f5}^{2}\mathrm{\ell}))$.
Multipass Streaming Models
Another interesting open problem would be to consider multiple pass streaming models. For the reasons outlined above, it seems like our lower bounds would be difficult to generalize to even a twopass streaming model. This leads to the interesting question of whether or not there are better algorithms in this model. At the very least, it is easy to see that the standard uniformity and closeness testers can be implemented with optimal sample complexity, $O(\mathrm{log}(n/\u03f5))$ memory, and $n$ passes over the data. What can be done with an intermediate number of passes?
Communication Lower Bounds for Closeness Testing
We would like to show communication lower bounds for closeness testing that are not implied by our uniformity testing lower bounds and the general sample complexity lower bounds. Our current adversary method is not sufficient for this task, as the testers that we have can distinguish our adversarial distributions from uniform in a small number of samples. In order to prove good closeness lower bounds, a more complicated adversary is necessary, and it is unclear how to combine this adversary with our informationtheoretic arguments. It would even be interesting to make progress in this question for the case of constant $\u03f5$.
Extending Ranges of Validity
An immediate open question is to extend the range of validity of many of our bounds. Both our algorithms and lower bounds only work for constrained ranges of parameters in ways that do not allow us to adequately cover the whole space of parameters. It would be interesting to see if this dependence could be removed. Another interesting parameter range would be to see if there are any streaming algorithms at all with $o(\mathrm{log}(n))$ memory.
InstanceOptimal/Adaptive Testing
[Valiant and Valiant(2014)] showed that testing identity to distributions other than the uniform distribution can often be done with better sample complexity in the centralized setting. It would be interesting to see what sort of analogue of this result can be obtained in our models. An analogous question can be asked for the adaptive closeness tester of [Diakonikolas and Kane(2016)].
I.D. is supported by NSF Award CCF1652862 (CAREER) and a Sloan Research Fellowship. This research was performed while T.G. was a postdoctoral researcher at USC, supported by I.D.’s startup grant. D.K. is supported by NSF Award CCF1553288 (CAREER) and a Sloan Research Fellowship. S.R. would like to thank Dheeraj P.V. for helpful discussions.
References
 [Acharya et al.(2015)Acharya, Daskalakis, and Kamath] J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. In Advances in Neural Information Processing Systems (NIPS), pages 3591–3599, 2015.
 [Acharya et al.(2018a)Acharya, Canonne, and Tyagi] J. Acharya, C. L. Canonne, and H. Tyagi. Distributed simulation and distributed inference. CoRR, abs/1804.06952, 2018a. URL http://arxiv.org/abs/1804.06952.
 [Acharya et al.(2018b)Acharya, Canonne, and Tyagi] J. Acharya, C. L. Canonne, and H. Tyagi. Inference under information constraints I: lower bounds from chisquare contraction. CoRR, abs/1812.11476, 2018b. URL http://arxiv.org/abs/1812.11476.
 [Ahlswede and Csiszar(1986)] R. Ahlswede and I. Csiszar. Hypothesis testing with communication constraints. IEEE Trans. Inf. Theor., 32(4):533–542, September 1986.
 [Andoni et al.(2018)Andoni, Malkin, and Nosatzki] A. Andoni, T. Malkin, and N. S. Nosatzki. Two party distribution testing: Communication and security. CoRR, abs/1811.04065, 2018. URL http://arxiv.org/abs/1811.04065.
 [Batu and Canonne(2017)] T. Batu and C. L. Canonne. Generalized uniformity testing. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 880–889, 2017.
 [Batu et al.(2000)Batu, Fortnow, Rubinfeld, Smith, and White] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In IEEE Symposium on Foundations of Computer Science, pages 259–269, 2000. URL citeseer.ist.psu.edu/batu00testing.html.
 [Batu et al.(2004)Batu, Kumar, and Rubinfeld] T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In ACM Symposium on Theory of Computing, pages 381–390, 2004.
 [Braverman et al.(2016)Braverman, Garg, Ma, Nguyen, and Woodruff] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, STOC 2016, pages 1011–1020, 2016.
 [Canonne(2015)] C. L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015.
 [Canonne et al.(2016)Canonne, Diakonikolas, Gouleakis, and Rubinfeld] C. L. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing shape restrictions of discrete distributions. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pages 25:1–25:14, 2016.
 [Canonne et al.(2017a)Canonne, Diakonikolas, Kane, and Stewart] C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing bayesian networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 370–448, 2017a.
 [Canonne et al.(2017b)Canonne, Diakonikolas, Kane, and Stewart] C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing conditional independence of discrete distributions. CoRR, abs/1711.11560, 2017b. URL http://arxiv.org/abs/1711.11560. In STOC’18.
 [Canonne et al.(2018)Canonne, Diakonikolas, and Stewart] C. L. Canonne, I. Diakonikolas, and A. Stewart. Testing for families of distributions via the fourier transform. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 10084–10095, 2018.
 [Chan et al.(2014)Chan, Diakonikolas, Valiant, and Valiant] S. Chan, I. Diakonikolas, P. Valiant, and G. Valiant. Optimal algorithms for testing closeness of discrete distributions. In SODA, pages 1193–1203, 2014.
 [Chien et al.(2010)Chien, Ligett, and McGregor] S. Chien, K. Ligett, and A. McGregor. Spaceefficient estimation of robust statistics and distribution testing. In Innovations in Computer Science  ICS 2010, pages 251–265, 2010.
 [Cover(1969)] T. M. Cover. Hypothesis testing with finite statistics. Ann. Math. Statist., 40(3):828–835, 06 1969.
 [Daskalakis and Pan(2017)] C. Daskalakis and Q. Pan. Square Hellinger subadditivity for Bayesian networks and its applications to identity testing. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 697–703, 2017.
 [Daskalakis et al.(2013)Daskalakis, Diakonikolas, Servedio, Valiant, and Valiant] C. Daskalakis, I. Diakonikolas, R. Servedio, G. Valiant, and P. Valiant. Testing $k$modal distributions: Optimal algorithms via reductions. In SODA, pages 1833–1852, 2013.
 [Daskalakis et al.(2018)Daskalakis, Dikkala, and Kamath] C. Daskalakis, N. Dikkala, and G. Kamath. Testing Ising models. In SODA, 2018.
 [Devroye and Györfi(1985)] L. Devroye and L. Györfi. Nonparametric Density Estimation: The ${L}_{\mathrm{1}}$ View. John Wiley & Sons, 1985.
 [Devroye and Lugosi(2001)] L. Devroye and G. Lugosi. Combinatorial methods in density estimation. Springer Series in Statistics, Springer, 2001.
 [Diakonikolas and Kane(2016)] I. Diakonikolas and D. M. Kane. A new approach for testing properties of discrete distributions. In FOCS, pages 685–694, 2016. Full version available at abs/1601.05557.
 [Diakonikolas et al.(2015a)Diakonikolas, Kane, and Nikishkin] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Testing identity of structured distributions. In Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2015, pages 1841–1854, 2015a.
 [Diakonikolas et al.(2015b)Diakonikolas, Kane, and Nikishkin] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 1183–1202, 2015b.
 [Diakonikolas et al.(2016)Diakonikolas, Gouleakis, Peebles, and Price] I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Collisionbased testers are optimal for uniformity and closeness. Electronic Colloquium on Computational Complexity (ECCC), 23:178, 2016.
 [Diakonikolas et al.(2017a)Diakonikolas, Gouleakis, Peebles, and Price] I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Sampleoptimal identity testing with high probability. CoRR, abs/1708.02728, 2017a.
 [Diakonikolas et al.(2017b)Diakonikolas, Grigorescu, Li, Natarajan, Onak, and Schmidt] I. Diakonikolas, E. Grigorescu, J. Li, A. Natarajan, K. Onak, and L. Schmidt. Communicationefficient distributed learning of discrete distributions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 6394–6404, 2017b.
 [Diakonikolas et al.(2017c)Diakonikolas, Kane, and Nikishkin] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Nearoptimal closeness testing of discrete histogram distributions. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 8:1–8:15, 2017c.
 [Diakonikolas et al.(2018)Diakonikolas, Kane, and Stewart] I. Diakonikolas, D. M. Kane, and A. Stewart. Sharp bounds for generalized uniformity testing. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 6204–6213, 2018.
 [Fischer et al.(2018)Fischer, Meir, and Oshman] O. Fischer, U. Meir, and R. Oshman. Distributed uniformity testing. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 455–464, New York, NY, USA, 2018. ACM.
 [Garg et al.(2014)Garg, Ma, and Nguyen] A. Garg, T. Ma, and H. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Advances in Neural Information Processing Systems (NIPS), pages 2726–2734, 2014.
 [Goldreich(2016)] O. Goldreich. The uniform distribution is complete with respect to testing identity to a fixed distribution. ECCC, 23, 2016.
 [Goldreich(2017)] O. Goldreich. Introduction to Property Testing. Forthcoming, 2017. URL http://www.wisdom.weizmann.ac.il/~oded/ptintro.html.
 [Goldreich and Ron(2000)] O. Goldreich and D. Ron. On testing expansion in boundeddegree graphs. Technical Report TR00020, Electronic Colloquium on Computational Complexity, 2000.
 [Han et al.(2018a)Han, Mukherjee, Özgür, and Weissman] Y. Han, P. Mukherjee, A. Özgür, and T. Weissman. Distributed statistical estimation of highdimensional and nonparametric distributions. In 2018 IEEE International Symposium on Information Theory, ISIT 2018, pages 506–510, 2018a.
 [Han et al.(2018b)Han, Özgür, and Weissman] Y. Han, A. Özgür, and T. Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory, COLT 2018, pages 3163–3188, 2018b. URL http://proceedings.mlr.press/v75/han18a.html.
 [Jordan et al.(2016)Jordan, Lee, and Yang] M. I. Jordan, J. D. Lee, and Y. Yang. Communicationefficient distributed statistical learning. CoRR, abs/1605.07689, 2016.
 [Kannan et al.(2014)Kannan, Vempala, and Woodruff] R. Kannan, S. Vempala, and D. Woodruff. Principal component analysis and higher correlations for distributed data. In Conference on Learning Theory, pages 1040–1057, 2014.
 [Lehmann and Romano(2005)] E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Texts in Statistics. Springer, 2005.
 [Liang et al.(2014)Liang, Balcan, Kanchanapally, and Woodruff] Y. Liang, M. F. Balcan, V. Kanchanapally, and D. Woodruff. Improved distributed principal component analysis. In Advances in Neural Information Processing Systems (NIPS), pages 3113–3121, 2014.
 [Neyman and Pearson(1933)] J. Neyman and E. S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694706):289–337, 1933. doi: 10.1098/rsta.1933.0009. URL http://rsta.royalsocietypublishing.org/content/231/694706/289.short.
 [Paninski(2008)] L. Paninski. A coincidencebased test for uniformity given very sparselysampled discrete data. IEEE Transactions on Information Theory, 54:4750–4755, 2008.
 [Rubinfeld(2012)] R. Rubinfeld. Taming big probability distributions. XRDS, 19(1):24–28, 2012.
 [Tsybakov(2008)] A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 2008.
 [Valiant and Valiant(2014)] G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In FOCS, 2014.
 [Valiant(2011)] P. Valiant. Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927–1968, 2011.
 [Zhang et al.(2013)Zhang, Duchi, Jordan, and Wainwright] Y. Zhang, J. Duchi, M. Jordan, and M. J. Wainwright. Informationtheoretic lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems (NIPS), pages 2328–2336, 2013.
 [Zhu and Lafferty(2018)] Y. Zhu and J. Lafferty. Distributed nonparametric regression under communication constraints. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, pages 6004–6012, 2018.