Tel Aviv University, Israel Uri Meir Theory of computation Distributed
algorithms Theory of computation Streaming, sublinear and near linear time
algorithms

###### Acknowledgements.

The author would like to thank Rotem Oshman for valuable counsel, Noam Mazor
for very helpful discussions, and Ami Paz as well as the anonymous referees of
ITCS 2021 for their useful comments.James R. Lee 1 12th Innovations in
Theoretical Computer Science Conference (ITCS 2021) ITCS 2021 ITCS 2021
January 6–8, 2021 Virtual Conference 185 19

# Comparison Graphs: a Unified Method for Uniformity Testing

Uri Meir

###### Abstract

Distribution testing can be described as follows: $q$ samples are being drawn
from some unknown distribution $P$ over a known domain $[n]$. After the
sampling process, a decision must be made about whether $P$ holds some
property, or is far from it. The most studied problem in the field is arguably
_uniformity testing_ , where one needs to distinguish the case that $P$ is
uniform over $[n]$ from the case that $P$ is $\epsilon$-far from being uniform
(in $\ell_{1}$). The _sample complexity_ of a property is the amount of
necessary and sufficient samples to test for this property, and it is known to
be $\Theta\left(\sqrt{n}/\epsilon^{2}\right)$ when testing for uniformity.
This problem was recently considered in various restricted models that pose,
for example, communication or memory constraints. In more than one occasion,
the known optimal solution boils down to counting collisions among the drawn
samples (each two samples that have the same value add one to the count). This
idea dates back to the first uniformity tester, and was coined the name
“collision-based tester”.

In this paper, we introduce the notion of _comparison graphs_ and use it to
formally define a generalized collision-based tester. Roughly speaking, the
edges of the graph indicate the tester which pairs of samples should be
compared (that is, the original tester is induced by a clique, where all pairs
are being compared). We prove a structural theorem that gives a sufficient
condition for a comparison graph to induce a good uniformity tester. As an
application, we develop a generic method to test uniformity, and devise
nearly-optimal uniformity testers under various computational constraints. We
improve and simplify a few known results, and introduce a new model in which
the method also produces an efficient tester.

The idea behind our method is to translate the computational constraints of a
certain model to ones on the comparison graph, which paves the way to finding
a good graph: a set of pairs that can be compared in this model, and induces a
uniformity tester. We believe that in future consideration of uniformity
testing in new models, our method can be used to obtain efficient testers with
minimal effort.

###### keywords:

Distribution Testing; Uniformity Testing; Distributed Algorithms; Streaming
Algorithms; Comparison Graphs

##  1 Introduction

The field of property testing was initiated by [11, 26, 21] and concerns with
fast probabilistic algorithms that use query access to some large structure
(such as graphs, functions, distribution, etc.) in order to determines whether
a specific instance belong to a subclass of possible instances (e.g.,
connected graphs or monotone functions) or in some sense far from it.
Specifically for distributions, as formulated in [10], we are given random
samples from some unknown distribution, and we wish to decide with high
probability (over the random samples) whether it has some property, or it is
far from any distribution that does (typically we use $\ell_{1}$ as a distance
measure). Properties of distributions were excessively studied through the
years (see [19, 12] for excellent surveys). Until recently, the vast majority
of results were limited to the classic setting, where a _single_ processor is
given an oracle access, and performs the testing procedure. The measure of
complexity is based solely on the number of samples, as typically the running
time is polynomial in this number.

However, distribution testing can be very useful in different frameworks as
well. For example, suppose we have a sensor network taking some measurements
that need to be combined in order to make a decision about the subject of
these measurements, be it volcanic activity, seismic movements, or any form of
radiation.

Another framework where testing is useful, is under constrained memory. One
might try testing an object so big, that the number of samples needed is very
large. In that scenario, even if one might endure a lengthly sampling process,
storing all past samples at one given moment can be too costly. For example,
imagine a large telescope collecting data on infrared radiation in a pursuit
to discover new planets. These types of questions can be translated to a
_streaming model_ , where samples come as a stream, and one wish to store only
a small amount of data while reliably test for a property of the underlying
distribution.

When considering the relatively similar motivations for these cases, one might
even wonder about a combination of the two models, where multiple sensors
spread out in some area collect samples, each of which has bounded memory.
They will then need to process all available data within their memory
constraints, such that by the end of each time period - they are able to
report their individual findings concisely to some data center that aggregates
all information in order to make an important decision.

All of these questions are inherently multi-dimensional, in the sense that
many incomparable resources are in play: the number of players, the number of
samples, the memory space of each sensor, and even the amount of bits
communicated. Here, we focus our efforts, for the most part, on minimizing the
_sample complexity_ (or amount of samples per player, when multiple players
are involved), with other resources given as parameters.

This specification is well-motivated by the case where we have no shortage of
data we can sample from, and we wish to understand how long a sampling process
should take, as a parameter of the number of sensors we use and their
computational strength. Throughout the text, we focus on the task of
uniformity testing, a key problem in the field of distribution testing.

###### Uniformity testing.

The most studied family of problems in distribution testing is arguably
_identity testing_ , where we want to test whether the input distribution $P$
is equal to some fixed distribution $p$, or $\epsilon$-far from it (in
$\ell_{1}$), where $\epsilon$ is the proximity parameter of the problem. In
the heart of these problems stands the problem of _uniformity testing_ , where
$p=U_{\Omega}$. One evidence for the importance of uniformity testing was
shown in [16] and made more robust in [20]: it is actually complete for
identity testing, in the sense that testing identity to any fixed distribution
$p$ can be reduced to testing uniformity instead. On the other hand,
uniformity testing is a specific case of other problems such as closeness
testing and independence testing, so showing lower bounds for uniformity
testing would imply lower bounds for these problems. The classic version of
testing uniformity was settled for the case
$\epsilon=\Omega\left(n^{-1/4}\right)$ in [25], showing that
$\Theta\left(\sqrt{n}/\epsilon^{2}\right)$ samples are in fact sufficient and
necessary. [27] later showed this holds for all values of $\epsilon$.

###### Collision-based testers.

The problem of uniformity testing was implicitly introduced in the paper [22],
as a way to test the expansion of a graph: when simulating multiple short
random walks, and observing the distribution of the endpoint, one can connect
a uniform distribution over these endpoint to good expansion of the graph. To
solve uniformity, the _collision-based_ tester was introduced, where one
simply counts the number of pairs of samples that have the same value. This
tester was shown to have sample complexity of
$\Theta\left(\sqrt{n}\cdot\operatorname{poly}(1/\epsilon)\right)$, which is
turned out to be sub-optimal in terms of $\epsilon$. However, several years
after the question was settled, it was shown in [15] that the original
collision-based tester also achieves optimal sample complexity, using a finer
analysis.

The idea behind the collision-based tester is rather straightforward: when
comparing two samples from a distribution, the chance of both having the same
value (also referred as _collision probability_) relates to the $\ell_{2}$
norm of the distribution. It is a well-known fact that over a fixed set
$\Omega$, the uniform distribution has the minimal $\ell_{2}$ norm. It is also
rather easy to show that any distribution that is somewhat far from uniform
(in statistical distance), has a significantly larger $\ell_{2}$ norm. This
means that each comparison of two samples is an unbiased estimator of the
collision probability (having the right expectation), but with very high
variance. One would need to average over many such comparisons in order to
reduce the variance.

###### Other methods to test for uniformity

Over the years, numerous methods to test for uniformity have been proposed.
Some of them had different goals in mind, such as testing with very high
confidence, or in a multiparty model where each player gets a single sample
(sometimes even wishing to keep it private). These methods include counting
unique element [25], modified $\chi^{2}$ test [27], using the empirical
distance to uniformity [14], randomly hashing samples to a smaller domain [7]
and more. In both [13, 17], testers that aim to overcome different constraints
relied strongly on collision counting111These testers do not count collisions
per se, but they add other steps to the algorithm. The results also use a more
involved analysis. Considering it is also optimal in the classic setting, this
makes collision-based testing a prime candidate for a more generic method to
test uniformity, and hopefully adjust itself to different models easily.

###### Comparison graphs.

The original version of the collision-based tester takes a set of samples, and
use comparisons between _all pairs of samples_. This is well-suited for the
classic model, where one processor with no concrete limitations sees all the
samples, and is able to perform all possible comparisons.

However, in more constrained models, this simple task is inherently
impossible. For example, a memory-constrained tester cannot store all previous
samples in order to compare them with new ones. In the simultaneous model,
where each processor holds its own set of samples, a lot of communication
might be needed to compare samples that are held by different
processors.222For a specific pair of samples, this would require solving
equality. When observing the two _sets_ of samples held by the two processors,
one can imagine a disjointness-type problem, which intuitively should be hard
to solve accurately. In distributed models, such as CONGEST and LOCAL (see
[17]), the problem is defined where each player in a network holds a single
sample from a distribution (replacing one sample by a constant amount produces
similar behaviour). In these models, it is much cheaper for player to compare
their samples with those of a neighboring player, than it is to make such a
comparison with players that are far away (on the network topology).

To this end, we introduce the notion of _comparison graphs_. A comparison
graph is linked to a collision-based tester (or algorithm) as follows: the
vertices of the graph are the samples given as input, and the edges are pairs
of samples that are being compared. As stated above: in the classic model this
graph is typically the complete clique (all pairs of samples are compared).
Under constrained models, however, very specific edges (comparisons) are
allowed, whereas others are not. For example, if the sample $s_{1}$ is given
to one player, and the sample $s_{2}$ is given to another player in the
simultaneous model, no algorithm can presume to compare the two samples.

Equipped with the notion of comparison graphs, one can define a _collision-
based_ tester as a couple $(G,\tau)$, where $G=(V,E)$ is the comparison graph
that defines which comparisons are being made, and $\tau$ is a threshold
parameter. The algorithm is defined as follows: it counts the amount of
collisions observed, $Z$, and compares it to a threshold $T$ that depends on
$\tau$ and the amount of comparisons made (which is $\left|E\right|$).

###### Reliable collisions-based testers

In Section 4.1, we prove a structural theorem concerning with which sets of
comparisons are able to inspire a reliable test for uniformity based solely on
counting collisions. This is done by observing the comparison graph $G$. We
formulate sufficient conditions in terms of the graph $G$, that guarantee it
induces a good tester (when paired with the right threshold parameter $\tau$).
It turns out that two properties of a comparison graph $G$ are key: the first
is the number of edges, which represents the amount of comparisons being made;
the second one, somewhat surprisingly, is the number of $2$-paths in the graph
$G$, which encapsulates the amount of dependencies between different
comparisons being made.

Few of our testers rely on the same type of graph, that pops up multiple
times, for different reasons. To this end, we formulate Lemma 3.2, that
specifies the required parameters for a comparison graph of this type to
induce a good tester.

###  1.1 Examples of comparison graphs

It is interesting that the number of samples (the measure we usually wish to
minimize) does _not_ appear as a condition on our comparison graph directly.
However, as we see later in the text, it does play a role indirectly, as
simple inequalities connect the three graph quantities (see Section 5.1).

Our structural theorem basically shows that any comparison graph with enough
edges, but not-too-many $2$-paths induces a good uniformity tester. To better
understand the meaning of this, we fix the amount of edges, $\left|E\right|$,
and review a short list of examples for potential comparison graphs. We are
interested in the interplay between the amount of vertices (samples), edges
(comparisons made) and $2$-paths (dependencies created).

###### The clique graph.

The standard tester is actually the full clique, comparing each possible pair
of samples. In this dense graph we only need $\sqrt{\left|E\right|}$ vertices
in order to have $\left|E\right|$ edges. However, many $2$-paths (and
dependencies) are created along the way as well,
$\Theta\left(\left|E\right|^{3/2}\right)$. For this specific case, it is
already known the two affects can be balanced to obtain optimal (asymptotic)
sample complexity.

###### Disjoint cliques.

Another interesting graph (used in some sense in [17]) is actually a union of
disjoint cliques. This graph turns out to be quite useful. For once, it makes
perfect sense in a simultaneous model, where each player process her own
samples, sending a short summary to the referee. Surprisingly, it arises in
other models as well.

###### A perfect matching.

This graph relates to taking a fresh pair of samples each time we wish to make
a new comparison, which leaves us with a set of completely independent
collision indicators. Indeed, in this graph there are no $2$-paths at all. Not
only this tester minimizes the dependencies – it actually overdoes it. Doing
so, it pays a price in sample complexity: the number of vertices we have is
$2\left|E\right|$, much larger than the clique, for instance.

###### The star graph.

With a fixed number of edges, this graph is actually the way to _maximize_ the
amount of $2$-paths and dependencies – which makes it a very poor comparison
graph. This makes perfect sense, as the tester described is equivalent to
drawing one element from $P$, and comparing it to many other samples,
basically assessing the probability of this element. This test can be shown to
perform poorly against specific distributions. e.g., if $P$ has probability
$1/n$ for _most_ elements. In this case we are very likely to draw such an
element first, and from here on every comparison has a $1/n$ chance to show a
collision. This would make $P$ indistinguishable from the uniform
distribution, even though it might be very far from it in practice.

###### The full bipartite graph.

Another graph that could be considered is the full bipartite graph,
$G=(V_{1}\sqcup V_{2},V_{1}\times V_{2})$. Here again we have a free parameter
(the size $\left|V_{1}\right|$, which determines
$\left|V_{2}\right|=\left|E\right|/\left|V_{1}\right|$). It ranges from a
star-graph (for $\left|V_{1}\right|=1$) to a balanced graph (for
$\left|V_{1}\right|=\left|V_{2}\right|=\sqrt{E}$), where the last one
functions asymptotically similarly to the clique. It appears that optimal
results for these graphs can be obtained through our framework only for the
balanced case.333By optimal here, we mean having “just enough” comparisons,
but no more. Once fixing $\left|E\right|$, a more imbalanced graph admits more
dependencies. Whenever $V_{1}=\omega(\sqrt{\left|E\right|})$, too many
dependencies are created and the theorem cannot be applied. This statement can
be formalized in a similar fashion to the results in Section 5.  To some
extent, such a tester was used in [13] to test uniformity in the streaming
model, storing the first batch of samples ($V_{1}$) then comparing the rest of
the stream ($V_{2}$) to this batch. Their result extends to a large range of
imbalanced graphs even when the number of comparison is small. However, their
tester in fact does a little more than counting collisions, as it first
examines the entire sample set $V_{1}$ and in some cases decides to abort.
This additional step is also integrated strongly in the analysis, which leads
us to believe the tester would not achieve its goal without it. In Section
3.2, it is shown that one can test uniformity in the streaming model via
collisions with no additional steps, using a whole different comparison graph.

The examples raise another inherent question: is it always better to add edges
in a graph with a fixed number of vertices (that is, after making a set of
comparisons $E$, can it hurt to add more comparisons to the calculation?)
Intuitively, adding edges seems to only improve the performance of the
algorithm. Proving a statement of the sort could better our understanding and
point towards optimal comparison graphs under certain constraints. In Appendix
A we discuss the matter and explain why such a statement is not true, at least
if one goes through our structural theorem to prove correctness of a
collision-based tester.

###  1.2 Models and Results

Our main result is a method that produces well-performing uniformity testers
in various models. In this paper we show a list of uniformity testers in
different models, specified below. We also show limitations of our method for
most of these models, which point towards a conclusion that no better
comparison graphs could have been chosen (up to constant factors in the sample
complexity of the induced tester). These limitation rely on a conjecture that
in some sense no matter the shape of the comparison graph, enough comparisons
always must be made.

We emphasize that for any model in which a lower bound is known (for any
method, not necessarily collision-based testing), the testers produced by our
method are optimal, up to $\operatorname{poly}(1/\epsilon)$ factors. As far as
we know, no testers in the literature are tight with the current lower bounds
for these specific cases. Thus, it could be the case that collision-based
testing achieves optimal results (even in terms of $\epsilon$) for all the
models we consider. A more thorough discussion is given in Section 5.3.

Equipped with a structural theorem, proven in Section 4.1, we consider various
models and devise a uniformity tester in each one. The key idea here is to
translate the constraints of each model into the comparisons we are able to
perform, or differently put: a structural limitation on the comparison graph.
Doing so will guide us how to choose a “good” comparison graph for this
specific model. Having a structure in mind, two formalities are left: (i)
Prove that calculation of $Z,T$ (the number of collisions, and the threshold
value) can be done in the model; (ii) Calculate our desired complexity measure
(which changes from model to model), and optimize the parameters of the chosen
graph (e.g., if the graph is a clique, determine the size of the clique).

###### Standard processors.

In Section 3.1, we deal with the classic and the simultaneous model. First we
use the classic model as a warm-up. Since this is done in [15], we add to the
mix a small insight: our framework (which allows the tester to choose
threshold values other than $\tau=1/2$) actually provides slightly better
constants when placing the threshold much lower (at roughly $\tau=1/9$).

For this model, it was shown by [14] that testing with high precision can be
done faster than it would have using standard amplification. However, they use
estimation of the empirical distance from uniform over the sample set. It is
unclear whether collision-based testing is fit for this task. We do not pursue
this direction here.444One reason is that our work focuses on the regime that
uses new and different comparison graphs, other than the clique graph. This
direction would probably involve analysis that is specific for the clique
graph, where all samples can be compared with one another.

We then move to the simultaneous case where multiple players each send a short
message to the referee, based on their own samples. The referee then needs to
output a decision about the underlying distribution. In this model we want to
find a good exchange for the number of players, the number of samples each
player gets, and the length of the messages. For example, if the messages can
be arbitrarily long, each player can send her entire sample set and the
problem becomes trivial. For this reason, the two papers to first consider
(independently) testing in this model, had a very different focus. In a
preliminary version of [6, 7], only the case of a _single sample_ per player
was considered, and their algorithms indeed rely on different and interesting
strategies, but not collision counting – as this strategy is irrelevant for
this regime. In [17] a different approach was taken, where all messages were
fixed to a _single bit_ , but each player gets multiple samples (and in fact,
their algorithm does rely on collisions in some sense, but it does not count
them accurately, and does not fall under the umbrella of our definition for
collision-based testers).

For our use, as oppose to both these view, we allow both parameters to be
larger. We allow multiple samples per player, and show that using a short
message (not a single bit, but not much longer), one can devise an efficient
tester.

We also consider the asymmetric cost variant of this model, which naturally
arise when reducing to it from the LOCAL model, a standard model in the field
of distributed computing. To motivate this variant, we think of the sampling
process as a bottleneck, but now each player has her own sampling rate (some
players might draw samples much faster than others). If before we tried to
minimize the amount of samples per player, now we wish to minimize the overall
sampling time instead, and still sample enough data to successfully test for
uniformity. More about the model and the reduction from the LOCAL model can be
found in [17].

We remark that many works in the simultaneous model consider communication
trade-offs, when assigning only a _single_ sample for each party. Our method
does not currently extend to this framework, although one might consider
integrating it with other methods. For example, one method (e.g., in [7]) uses
random hash to a smaller domain. One might consider collisions on this domain
instead of the original one. these meta-collisions can be counted within the
communication constraints.

Some works in this regime (single sample) focus on privacy aspects of testing
(e.g., [2, 8]). This line of research should be irrelevant for our method (and
even the extension mentioned above), as any detection of a collision (even on
a smaller domain) would immediately give away non-trivial information about
the sample.

###### Memory-constrained processors.

In Section 3.2, we deal with a different type of processors: _memory-
constrained_ processors. When observing a single processor of this type, we
end up with the streaming model (as described in [13]). At least one scenario
which motivates the simultaneous model is seemingly very coherent with such
constrained processors. Thinking of a network of sensors, or remote devices,
gathering samples – it is quite comprehensible that these processors are not
only limited by their ability to communicate with the data center, but also by
their ability to store the entire data observed between consecutive reports
(in this scenario, the data center is the referee performing the test
periodically to detect anomalies). For this reason, we also consider the case
of a simultaneous model, where each processor has a small memory budget. In
this new model, we easily devise again an efficient uniformity tester.

###### Testing in an interactive model.

Lastly, in Section 3.3, we use the structural theorem to show how on certain
graphs one can solve uniformity in the CONGEST model faster than what was
previously known to be possible. Specifically, if the communication network
has $k$ players and diameter $D$, and each players start with one sample, the
best known algorithm runs in $O(D+n/(k\epsilon^{4}))$ rounds [17]. The
improvement we suggest is an algorithm that takes $O(D)$ rounds, and works in
specific networks that have a certain topological characteristics. Moreover,
we show a simple detection procedure of $O(D)$ rounds, that can be used to
recognize such a good topology. This means that _any_ network can use the
detection procedure first, and then either proceed as in [17], or switch to
the faster ($O(D)$) algorithm whenever it is guaranteed to perform well.

###  1.3 Related Work

The task of uniformity testing, as well as the collision-based tester for it,
were introduced in [10] (and implicitly in [22]). Later on, upper and lower
bounds on the sample complexity of the problem were given by [25] (for most
values of $\epsilon$), showing that the optimal sample complexity is in fact
$s=\Theta\left(\sqrt{n}/\epsilon^{2}\right)$, where $n$ is the world size, and
$\epsilon$ is a proximity parameter. A preliminary version of [27] giving a
tester that achieves this complexity for any value of $\epsilon$. The last two
papers used two different testers: the first relied on the number of
_distinct_ elements in the sample set (this test is somewhat dual to counting
collisions), and the second on a modified $\chi^{2}$ tester. It was then shown
by [15] that the collision-based tester does in fact achieve optimal sample
complexity too.

In the past few years there has been a growing interest in distribution
testing under various computational models, including collaborative testing in
multiparty model, the streaming model, privacy aspects of testing, and others
([6, 7, 17, 9, 2, 23, 4, 5, 1, 24, 18, 8] and more). We mention in more
details the works concerning uniformity testers in models we pursue.

In a preliminary version of [6, 7] and [17] each, independently, the task of
uniformity testing was considered in a simultaneous communication model. In
this model, all players receive samples from the same global distribution $P$,
and all players report to a referee based on their own samples. The referee in
turn uses the reports to output (with high probability) whether $P$ holds some
property.

In both lines of work, the focus was uniformity testing, but using two
different perspectives: the former zeroes in on one sample per player, where
the trade-off in question is between the number of bits each player is allowed
in his report, and the number of players needed to the testing process. We
think of the number of bits as too small to describe the sampled element
fully. In this setting, a full description of two samples is never available
to a single player (nor the referee, whenever no player can describe fully the
element it samples). We do note that the tester given there relies on a looser
notion of collisions (Taking a coarser division of $[n]$ into subsets).

In the later, the focus is different: one now fixes instead the communication
to _one_ bit per player. Now, the trade-off is between the number of players
and the number of samples each one of them takes. The upper bound devised
there discuss each player taking the right amount of samples, and notifying
the referee $0$ if no collision occurred, and $1$ otherwise. In some sense,
the referee ends up counting collisions (notice the count is trimmed, as one
player might see more than $1$ collision, but is only able to report 0 or 1).
This tester is then used as a black-box to solve uniformity testing in the
classic distributed models (CONGEST, and LOCAL), in a setting where each
player initially draws one sample.

One other paper to specifically discuss uniformity testing is [13], in which a
streaming version of the problem is defined, as well as another distributed
version, in a blackboard model, where all players are privy to the messages
sent by others. As opposed to the simultaneous models mentioned above – here
several rounds of communication are allowed. As it turns out, the streaming
algorithm, as well one of two algorithms suggested for the distributed
version, boil down yet again to counting collisions under the limitations of
the model.

In addition to these, quite a few works had the focus of showing impossibility
results both in the classic and the entire variety of models. For out
interest, we mention [16, 25] for the classic version, as well as [23] for the
simultaneous model (with multiple samples per machine), and [13, 4] for the
streaming model.

##  2 Preliminaries

Throughout this text, we discuss uniformity testing using collision-based
testers.

We let $[n]:=\left\\{1,2,\dots,n\right\\}$, and use $\Delta([n])$ to denote
the set of distributions over the set $[n]$. As we only care about the support
size (rather than the values), it is enough to consider $P\in\Delta([n])$ as
possible input distributions. For a distribution $P$ over $[n]$, we write
$P_{i}$ for the probability of the $i^{th}$ element.

An $(n,\epsilon)$-uniformity tester is an algorithm $\mathcal{A}$ that given
oracle access to some unknown distribution $P\in\Delta([n])$, takes
$q=q(n,\epsilon)$ samples from $P$ and satisfy the following:

  * •

If the input distribution is $P=U_{n}$, the uniform distribution over $[n]$,
then $\mathcal{A}$ outputs YES with probability at least $3/4$.

  * •

If $\left\|P-U_{n}\right\|\geq\epsilon$, which means the distribution $P$ is
$\epsilon$-far from uniform), then $\mathcal{A}$ outputs NO with probability
at least $3/4$.

The distance used here is $L_{1}$. Meaning, for two distribution $P,Q$, the
distance is $\left\|P-Q\right\|=\sum_{i=1}^{n}\left|P_{i}-Q_{i}\right|$.

To formalize our notion of a _collision-based_ tester, we take a fresh point
of view of the sampling process. The key object in our analysis is the
_comparison graph_ , which is simply an undirected graph $G=(V,E)$, where we
think about $V$ as a set of placeholders for samples and $E$ as the pairs of
samples which are chosen to be compared with one another.

######  Definition 2.1 (Sampling process, collision indicators).

Given a comparison graph $G=(V,E)$ and an input distribution
$P\in\Delta([n])$, the sampling procedure $S_{P}$ is described as a random
labeling of the vertices according to $P$. We denote by $S_{P}:V\to[n]$, the
process for which $\forall i.S_{P}(v_{i})\sim P$, independently from one
another. We end up with $S_{P}(v_{1}),\dots,S_{P}(v_{{}_{\left|V\right|}})$
which is a set of $\left|V\right|$ i.i.d samples from $P$.

Moreover, for every edge $e=(u,v)$ in $E$ we define a unique indicator, we
call the collision indicator and denoted by
$\mathds{1}_{e}^{P}:=\mathds{1}_{S_{P}(u)=S_{P}(v)}$.

When $P$ is clear from context, we simply write $S(u)$ for the sample
associated with vertex $u$, and $\mathds{1}_{e}$ for the collision indicator
of the edge $e$.

We are now ready to give a formal definition for a collision-based tester,
which relies on a set of comparisons (not necessarily between all pairs of
samples), and compares $Z$ \- the amount of collisions, with some threshold
value $T$.

######  Definition 2.2 (Collision-based tester).

Fix $n,\epsilon$. For any comparison graph $G=(V,E)$ and real number
$0\leq\tau\leq 1$, we define the algorithm as follows: upon receiving as input
$\left|V\right|$ i.i.d samples from $P$ (given by
$S_{P}(v_{1}),\dots,S_{P}(v_{{}_{\left|V\right|}})$), it computes the
following:

$\displaystyle Z$ $\displaystyle:=\sum_{e\in E}\mathds{1}_{e}\ ,$
$\displaystyle T$
$\displaystyle:=\left|E\right|\cdot\left(\frac{1+\tau\epsilon^{2}}{n}\right)\
,$

and outputs YES if $Z<T$, and NO otherwise.

The restriction $\tau\in[0,1]$ will help us deal with technicalities, but we
note that it is rather intuitive. Indeed, as we will see later, only for these
values the expectation of $Z$ is lower than $T$ for the good input (uniform
distribution), and higher than $T$ for _all_ bad inputs.

Throughout, we will focus on properties of the graph and of our input
distribution. We denote by $\left|E_{G}\right|$, $\left|V_{G}\right|$ the
number of edges and vertices in $G$, and by $c(G)$ the number of times a
2-path appears as a subgraph in $G$. We count each 2-path twice, for its 2
automorphisms, and so we need to count “directed” $2$-paths (so $e_{1},e_{2}$
and $e_{2},e_{1}$ are both counted). Formally, we can write
$c(G)=\left|\left\\{(u,v,w)\in\binom{V}{3}\medspace|\medspace(u,v),(v,w)\in
E\right\\}\right|$.

For the distribution $P$ over $[n]$, with $P_{i}$ for the probability of the
$i^{th}$ element, we denote the collision probability
$\mu_{P}=\sum_{i=1}^{n}P_{i}^{2}$, and the three-way collision probability
$\gamma_{P}=\sum_{i=1}^{n}P_{i}^{3}$. For brevity, whenever $G$ or $P$ are
clear from context, we simply write $\left|V\right|$, $\left|E\right|$, $\mu$,
$\gamma$.

###  2.1 Models of Computation

In all our results we are concerned with distribution testing (and
specifically uniformity testing), and we deal with various models. Therefore,
in the following lines we specify in which way samples are taken in each
model, and in what way the answer of the algorithm needs to be declared (where
a good tester is the one that outputs YES (resp. NO) with high probability
whenever the samples are taken from a YES (resp. NO) distribution).

###### The centralized model.

The centralized model is the classic model. In this model one processor
receives all samples $s_{1},\dots,s_{q}$ (in comparison graph notations, we
think of $s_{i}=S(v_{i})$, and $q=\left|V\right|$), and is tasked with
outputting a proper answer according to the underlying input distribution. The
complexity measure we wish to minimize in this model is $q$, the number of
samples.

###### The simultaneous model.

The second model we consider is the simultaneous model, where $k$ players
(processors) each draw individual samples unseen by all other players. Each
player sends a short message to the referee. The referee then aggregates the
messages and outputs the answer. Formally, each player is tasked with $V_{i}$
where the whole set of vertices in $G$ is $V=\sqcup_{i=1}^{k}V_{i}$. The
samples of processor $i$ are then $\left\\{S(v)\right\\}_{v\in V_{i}}$. Each
processor can send a message $a_{i}$ which is a function of its samples, and a
referee receives all messages $a_{1},\dots,a_{k}$ and outputs the answer. The
simultaneous first appeared in the context of testing independently in [17]
and preliminary version of [6, 7], where in the first $\left|a_{i}\right|=1$
meaning each player is allowed to send one bit, and in the latter
$\left|V_{i}\right|=1$ meaning each player gets exactly one sample. We take
the same point of view as in [17], but we remove the restriction of $1$ bit
and allow a longer (but still short) message instead.

The number of players $k$ is given as a parameter, and our goal is to minimize
the number of samples _per player_ , where all players get the same amount of
samples: $q/k$ (we think of it as sort of parallelization of the sampling
process). We also consider the asymmetric-cost variant, where each player has
an individual cost for each sample it draws (we think of this cost as the time
it takes to draw each sample), and we wish to minimize the cost (or time) of
the entire sampling process.

We also discuss the case of memory-constrained processors, also referred to as
the streaming model, where this distribution testing was recently considered
in [13].

###### Memory-constrained processor.

In the memory-constrained model each processor receives its samples as a
stream, and once a sample is dealt with it is gone forever (this is the one-
pass variant of the streaming model). A processor can only use a limited
amount at each given moment, denote by $m$ (and measured by memory bits). We
think of $m^{\prime}=\lfloor m/(2\log n)\rfloor$ as the number of samples we
can store with half the memory (we leave the other half for other
calculations). The complexity measure of this model is the number of samples
needed to complete the testing task.

Next we consider a new model that poses both constraints. It is a simultaneous
model where each processor is memory-constrained, receiving its samples as a
stream, and using its $m$ bits of memory it needs to come up with a message
$a_{i}$ to send to the referee once all samples are seen. The referee then
receives all messages and outputs an answer. We stick to the case where all
processors are of the same type and therefore have the same constraints of $m$
bits.

###### The CONGEST Model.

A standard model in the field of distributed computing is the CONGEST, where
we have a communication network with $k$ players, and the networks runs a
protocol that halts once a task is done. The complexity measure for this model
is the number of communication round, and the focus is on congestions, as each
communication edge can only transfer a small amount of bits at each round. In
[17] the task of testing in this model was considered and formulated in the
following way: We have $k$ players over some communication graph, and each
player is given one sample from an unknown distribution $P\in\Delta([n])$. The
players wish to run a communication protocol that ends when some player knows
(with high probability) whether $P$ has some property, or is $\epsilon$-far
from it. We assume here that $k=\Omega(n/\epsilon^{2})$ (as otherwise, the
task becomes impossible), and we wish to minimize the amount of communication
rounds, where at each round only $\Theta\left(\log n+\log k\right)$ bits can
be communicated over each communication edge.

##  3 Results

In this section we go over numerous applications of our method. For each model
we go over the same phases: we start with intuition as to which comparison
graph $G$ is fit to this model, and we go on to show how one can simulate a
collision-based algorithm . By simulating the algorithm we mean that by the
end of the calculation, some processor will be able to compute both the number
of collisions ($Z$) and the fitting threshold ($T$), so it is able to output
the answer. The last part is optimizing parameters, where first order
parameters are those of $G$, and in some application we also give focus to
second order parameters (choosing $\tau$).

The strength of the method comes from the following structural theorem that
gives sufficient conditions for a comparison graph inducing a good uniformity
tester:

######  Theorem 3.1.

Fix a domain size $n$ and a proximity parameter $\epsilon$. If the following
hold for an algorithm :

  1. 1.

$\left|E\right|\geq\frac{4n}{\tau^{2}\cdot\epsilon^{4}}$,

  2. 2.

$\left|E\right|\geq\frac{16n}{(1-\tau)^{2}\cdot\epsilon^{4}}$, and

  3. 3.

$\frac{c(G)}{\left|E\right|^{2}}\leq\frac{(1-\tau)^{2}\epsilon^{2}}{16\sqrt{n}}$,

then is an $\epsilon$-uniformity tester.

The proof, for the most part, is a generalization of the one used in [15] to
show the original collision-based tester is optimal (in our notations, the
original tester over $q$ samples is simply the algorithm ). While generalizing
the proof we leave not one, but _three_ separate conditions on a general
comparison graph, that together guarantee it induces an
$(n,\epsilon)$-uniformity tester. This supplies a better, multi-dimensional
understanding of how well a collision-based algorithm is guaranteed to
perform. We note that if one is willing to ignore constants, one could simply
fix $\tau=1/2$ and merge the first two conditions into one. However,
interestingly for our method other values of $\tau$ (usually smaller)
guarantee slightly better constants. We leave all $3$ conditions separate to
maintain maximum flexibility when proving application of the theorem.

A specific comparison graph that is key to our algorithms is the one of
_disjoint cliques_. Indeed, our strategy will be “perform any comparison you
can” which sometimes simply means we have several bulks of samples, where in
each bulk all pairs can be compared. To this end, we give a more specific
version of Theorem 3.1, for graphs that have this structure:

######  Lemma 3.2.

Fix $n,\epsilon$. Fix a comparison graph $G=\bigsqcup_{i=1}^{\ell}G_{i}$,
where each $G_{i}$ is isomorphic to $K_{q}$, for some $q\geq 3$. If the
following hold for an algorithm :

  1. 1.

$q\sqrt{\ell}\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\epsilon^{2}}$

  2. 2.

$q\sqrt{\ell}\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\epsilon^{2}}$

  3. 3.

$q\ell\geq\frac{24\sqrt{n}}{(1-\tau)^{2}\epsilon^{2}}$

then is an $\epsilon$-uniformity tester that uses $\left|V\right|$ samples.

Here again we leave the $3$-conditions version in order to be able to adjust
the threshold parameter for optimizations. However, here all $3$ conditions
are quite similar, pointing to the following simple corollary:

######  Corollary 3.3.

Fix $n,\epsilon$. Fix a comparison graph $G=\bigsqcup_{i=1}^{\ell}G_{i}$,
where each $G_{i}$ is isomorphic to $K_{q}$, for some $q\geq 3$. For each
constant $\tau$, the algorithm is an $\epsilon$-uniformity tester, if it holds
that

$q\sqrt{\ell}\geq 35\sqrt{n}/\epsilon^{2}$

######  Proof 3.4.

As $\ell\geq 1$, we have $q\ell\geq q\sqrt{\ell}$, and so the third condition
can be relaxed in that manner. By fixing a constant value $\tau=1/9$, all $3$
conditions of the lemma boils to the same asymptotic term with constant less
than $35$ (and a slightly better guarantee can be made by optimizing over
$\tau$).

We are now ready to devise testers in various models.

###  3.1 Standard Processors

####  3.1.1 Centralized Model

As a warm up, we re-prove the original collision-based tester works, in term
of the comparison graph, and using 3.2. To add a small twist, we show that
under our analysis, better sample complexity is guaranteed when using a biased
threshold (meaning, taking $\tau\neq 1/2$). Let us denote $q:=\left|V\right|$,
which is the number of samples drawn, and our complexity measure for the
model. The following is rather straightforward:

######  Corollary 3.5.

One can test uniformity using
$q=\Theta\left(\frac{\sqrt{n}}{\epsilon^{2}}\right)$.

######  Proof 3.6.

We simply use the lemma for $\ell=1$ (one big clique), and then sufficient
conditions on $q$ are:

  1. 1.

$q\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\epsilon^{2}}$

  2. 2.

$q\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\epsilon^{2}}$

  3. 3.

$q\geq\frac{24\sqrt{n}}{(1-\tau)^{2}\epsilon^{2}}$

All of which are fulfilled by choosing e.g.,
$q=\frac{100\sqrt{n}}{\epsilon^{2}}$ with $\tau=1/2$. We note that the tester
can easily compute $Z,T$ and therefore execute the collision-based algorithm
$(G,\tau)$, for any value of $\tau$.

An added perk here, is that one can optimize $\tau$ over the three conditions
to reduce sample complexity by a constant factor. Even though the guaranteed
constant is somewhat of an artifact of the proof, it is still interesting to
see that $\tau=1/9$ would reduce the constant from $100$ to roughly $35$
(while simple optimization over $\tau$ would reduce it even a bit more, for
some irrational threshold value).

####  3.1.2 Simultaneous Model

In this section we discuss the simultaneous model, where $k$ players are each
given oracle access to the distribution $P$. After taking samples, each player
is allowed to send a short message to a referee, who then needs to output the
right classification for $P$ (with high probability).

We give our focus to the variant posed in [17]: what is the number of _samples
per player_ needed to test uniformity? The “single collision” algorithm
devised for that question only requires _one bit_ from each player, and indeed
it was shown to be optimal in [23]. However, this algorithm is somewhat
delicate: first, the range of the parameter $k$ is limited (it cannot be too
high or too low, with regards to $n,\epsilon$); second, if the number of
players $k$ is not accurately known to all players, the algorithm breaks. This
is because unlike most results in the classic setting, the analysis here
actually requires each player to use a specific amount of samples, but not
more or less. Because the players can only communicate a single bit,
everything else must be set in advance given the problem’s parameters.

To that end, we relax the model, and allow each player to send a small number
of bits. These would allow each player to send the number of collisions she
saw (rather than _whether_ a collision occurred). Our algorithm works for any
parameter $k$, and can adjust to the case where each player is not exposed to
the exact value of $k$, but rather to an approximation of it.

The model at hand imposes very concrete limitations on our comparison graph:
one cannot compare a sample from one process to a sample of the another
process. This means having $k$ players solving the problem in a parallel way,
is equivalent to having a comparison graph whose number of connected
components is _at least_ $k$. Followed by the intuition of “compare every pair
you have”, the graph we use is the disjoint cliques graph, with $k$ disjoint
cliques. Our measure of complexity is the number of samples each player used,
$q^{\prime}$, which is translated to be the size of each one of our cliques.

######  Corollary 3.7.

In the simultaneous model, one can test uniformity using
$q^{\prime}=\Theta\left(\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right)$ samples
per player, where each player is allowed to send
$\Theta\left(\log\left(1/\epsilon\right)\right)$ bits to the referee.

######  Proof 3.8.

We again turn to the structured graph of Lemma 3.2, where each player uses an
independent sample set of size $q^{\prime}$ and compares all the pairs. We
have $k$ players in total doing so.

Our first goal is to show how to simulate a collision-based tester $(G,\tau)$
in this model. This will be possible whenever $G$ is made of at least $k$
vertex-disjoint connected components $G=\bigsqcup_{i\in[k]}G_{i}$.

The first simple observation is that each player can operate on a designated
part of the graph $G_{i}=(V_{i},E_{i})$. Meaning, the $i^{th}$ player is able
to compute $Z_{i}:=\sum_{e\in E_{i}}\mathds{1}_{e}$ by using her partial
sample set, $V_{i}$.

We next note that $Z=\sum_{i}Z_{i}$, and so if every player communicates
$Z_{i}$ to the referee “well enough” – she can go on to compute $Z$. Computing
$T$ is easy: the algorithm is known to all, and specifically the values
$\tau,\left|E\right|$ are known to the referee. The last part is comparing the
values and output the decision $\mathds{1}_{Z<T}$.

Our next step is to quantify the communication and sampling cost of said
algorithm. We aim at a communication cost of $\log\left(1/\epsilon\right)$
bits per player. We would like each player to send the value $Z_{i}$. However,
this value might be too high, especially for the case of distributions with
very high collision probability (which are also very far from being uniform).
To this end, we present the following simple observation:

######  Observation 1.

To simulate a collision based algorithm $(G,\tau)$ in the simultaneous case,
it suffices for each player to send $\log\left(T\right)$ bits. Indeed,
whenever $Z_{i}>T$, we know that $Z>T$ as well, and a special string can
signal the referee to reject.

We now calculate the sample complexity, measured in samples _per player_. We
use Lemma 3.2 with $q^{\prime}$ and $\ell=k$, to know that it is enough if we
satisfy:

  1. 1.

$q^{\prime}\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\sqrt{k}\epsilon^{2}}$

  2. 2.

$q^{\prime}\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\sqrt{k}\epsilon^{2}}$

  3. 3.

$q^{\prime}\geq\frac{24\sqrt{n}}{(1-\tau)^{2}k\epsilon^{2}}$

Which is enough to show the asymptotic sample complexity we desire.555Assuming
large enough $k$, the third condition pose asymptotically weaker requirement,
and so optimizing $\tau$ on the first two would yield the optimal guarantee
for $\tau=1/3$, getting us to
$q^{\prime}=\left\lceil\frac{\sqrt{108}\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right\rceil$
samples per player.

Since the third condition is looser than the first two, we actually choose the
number of samples per player, $q^{\prime}$, such that
$\left|E\right|=\Theta\left(n/\epsilon^{4}\right)$. Since
$\tau\epsilon^{2}\leq 1$, this means that our threshold is not too large

$T=\Theta\left(\frac{n}{\epsilon^{4}}\right)\cdot\left(\frac{1+\tau\epsilon^{2}}{n}\right)=\Theta\left(1/\epsilon^{4}\right),$

and so, using the observation, the simulation of the algorithm only requires
each player to send $\log\left(\Theta(1/\epsilon^{4})\right)$ bits to describe
the number of collisions she saw.

######  Remark 3.9.

As apparent from [6, 7, 23], when messages are $r$ bits long, the correct
value to look for in the sample complexity is $2^{r}$ (and sometimes
$\sqrt{2^{r}}$). For this reason, when discussing communication, we explicitly
write expressions such as $\log\left(\Theta(1/\epsilon^{4})\right)$ instead of
a more general $\Theta\left(\log(1/\epsilon)\right)$. This would prove useful
when comparing our results to known lower bounds, as is done in Section 5.3.

######  Remark 3.10.

For the oblivious case where the players only know an approximation for the
number of players, $k$, each player would also need to send the referee the
amount of comparisons she has made. We note that sending the amount of samples
is enough, but still doing so naively raises the communication cost from
$\log\left(\Theta(1/\epsilon^{4})\right)$ to
$\log\left(\Theta(n/\epsilon^{4})\right)$.

To avoid this, we suggest an alternative: each player rounds up her number of
samples to the nearest power of $2$, and sends the power instead, so the
referee can derive the exact number of samples (and therefore comparisons).
For the number of collisions we could not have used the same trick, as it must
be sent _accurately_. To conclude, in the oblivious case, we can still perform
uniformity testing with communication
$\log\left(\Theta(1/\epsilon^{4})\right)+\log\log\left(\Theta(n/\epsilon^{4})\right)$
per player, while increasing the amount of samples (of each player) by a
factor of at most $2$ (rounding to the nearest power).

####  3.1.3 Asymmetric-Cost Model

This variant is best described and motivated as follows: we think of the
sampling process as time consuming, and each of the $k$ players now has her
own sampling rate, meaning that some players are able to draw samples faster
than others. We describe the sampling rate vector $R=(R_{1},\dots,R_{k})$, and
we let each player draw her own number of samples $(s_{1},\dots,s_{k})$. The
complexity measure is the time dedicated for the sampling process, denoted
$t$. Within $t$ time, player $i$ collects exactly $q_{i}:=\lfloor R_{i}\cdot
t\rfloor$ samples.

Executing the tester works just as before. If the referee knows
$(R_{1},\dots,R_{k})$, and the time $t$, she can calculate the threshold
correctly, and as before - $Z=\sum_{i}Z_{i}$, where $Z_{i}$ is communicated by
player $i$. The big difference here is the analysing the complexity measure,
$t$. Note that the algorithm now assigns more responsibility to players who
can obtain more samples within the same period of time.

To this end, we tweak the disjoint cliques graph in a way that each clique has
a different size, relating to the sampling rate of said player. This would
lead us to the following corollary:

######  Corollary 3.11.

In the simultaneous model, one can test uniformity in time
$t=\Theta\left(\frac{\sqrt{n}}{\epsilon^{2}\left\|R\right\|_{2}}\right)$,
where $\left\|R\right\|_{2}=\sqrt{R_{1}^{2}+\dots+R_{k}^{2}}$, and each player
is allowed to send $\Theta\left(\log\left(1/\epsilon\right)\right)$ bits to
the referee.

######  Proof 3.12.

Our graph is now $G=\bigsqcup_{i\in[k]}G_{i}$, where $G_{i}$ is a clique on
$q_{i}=R_{i}\cdot t$ vertices. We use the same observation as before, that no
player needs to send more than $\log\left(T\right)$, where $T$ is the
threshold of the algorithm $(G,\tau)$.

In terms of the whole graph $G$, we have: $\left|V\right|=\sum_{i}q_{i}$. We
have the bound

$\left|E\right|=\sum_{i}\frac{q_{i}^{2}-q_{i}}{2}\geq\frac{\sum_{i}(q_{i}^{2})}{3}=\frac{t^{2}\cdot\left\|R\right\|_{2}^{2}}{3},$

as well as the bound

$c(G)=\sum_{i}\binom{q_{i}}{3}\leq\frac{\sum_{i}q_{i}^{3}}{6}=\frac{t^{3}\cdot\left\|R\right\|_{3}^{3}}{6}\leq\frac{t^{3}\cdot\left\|R\right\|_{2}^{3}}{6}.$

Combining the two we have

$\frac{\left|E\right|^{2}}{c(G)}\geq\frac{t^{4}\left\|R\right\|_{2}^{4}/9}{t^{3}\left\|R\right\|_{2}^{3}/6}=\frac{2t\left\|R\right\|_{2}}{3},$

and so sufficient conditions for Theorem 3.1 are:

  1. 1.

$t\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\left\|R\right\|_{2}\epsilon^{2}}$

  2. 2.

$t\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\left\|R\right\|_{2}\epsilon^{2}}$

  3. 3.

$t\geq\frac{24\sqrt{n}}{(1-\tau)^{2}\left\|R\right\|_{2}\epsilon^{2}}$

Which is enough to show the asymptotic number we desire. Again, the algorithm
uses $\left|E\right|=\Theta\left(n/\epsilon^{4}\right)$ comparisons, and
satisfy $T=O\left(1/\epsilon^{4}\right)$, which means each player needs to
send at most $\log\left(\Theta(1/\epsilon^{4})\right)$ bits to the referee.

This algorithm is actually a generalization of the previous two algorithms:
(1) if the rate vector is $R=(1,\dots,1)$, then $t$ is the number of samples
per player, and $\left\|R\right\|_{2}=\sqrt{k}$; (2) if the rate vector is
$R=(1,0,\dots,0)$, then only one player is actually taking samples, and indeed
$t\cdot\left\|R\right\|_{2}=t$ is the number of samples.

###  3.2 Memory-Constrained Processors

####  3.2.1 Centralized Model with Memory Constraints

In the streaming version of the problem, introduced in [13], we get the
samples from distribution $P$ in a stream, and can only store $m$ bits of
memory. We wish to stream as few samples as possible and still output with
high probability whether $P$ is uniform or $\epsilon$-far. For our purposes,
it will be useful to keep in mind the parameter of $m^{\prime}=\left\lfloor
m/2(\log(n))\right\rfloor$, the number of _samples_ that can be stored with
half of the memory space (the other half will be used to perform required
calculations).

The restriction this model imposes is that when a certain sample is being
processed, it can only be compared with the $O(m^{\prime})$ samples that are
currently stored. This intuition can be formalized to show that any comparison
graph used in the streaming model must have a bounded _average_ degree (the
maximal degree can be arbitrarily high, as one sample can be stored aside and
compared with all the rest). Indeed, we show this later on (see Claim 1, in
Section 5.2.2) when dealing with lower bounds for our method. However, for now
we merely use this intuition to choose a fitting comparison graph for the
model.

In [13] the bipartite tester was used, with one side much smaller than the
other. This graph goes along with the intuition, as it has a small average
degree. The bipartite tester was shown to achieve sample complexity of
$\Theta\left(n/(m^{\prime}\epsilon^{4})\right)$, which is shown to be optimal
for a specific range of values for the parameter $m$. It was left as an open
question whether this sample complexity can be attained for other values of
$m$. For the upper bound, we answer this question in the positive. We use not
only a different analysis, but rather a whole different comparison graph, one
that also has a low average degree. For simplicity, we again turn to the
disjoint cliques graph, having dealt with similar analysis in the previous
section (for the simultaneous model). However, we point out the fact that
another graph leads to slightly better guarantees (by a small constant
factor), with more cumbersome analysis.666The better comparison graph has the
vertex set $V=\left\\{1,\dots,q\right\\}$, and the slightly larger edge set
$E=\left\\{(i,j)\medspace|\medspace\left|i-j\right|\leq
m^{\prime}-1\right\\}$. The tester it induces stores $m^{\prime}$ samples at
any given moment. For any new element, it replaces it with the oldest one in
store ($m^{\prime}$ samples ago) and compares it to the other $m^{\prime}-1$
samples. Before this element is being removed, it is compared with
$m^{\prime}-1$ new samples that followed it. So other than the first and last
$m^{\prime}$ samples, each is being compared with $2m^{\prime}-2$ other
samples.

######  Corollary 3.13.

In the streaming model with memory $m$ , one can test uniformity using

$q=\Theta\left(\max\left\\{\frac{n\cdot\log(n)}{m\epsilon^{4}},\sqrt{n}/\epsilon^{2}\right\\}\right)$

samples, as long as we have $m=\Omega\left(\log(1/\epsilon)\right)$.

######  Proof 3.14.

Whenever we have enough memory
$m=\Omega\left(\sqrt{n}\log(n)/\epsilon^{2}\right)$, the dominating factor in
the statement is the second one, and indeed one can store the whole
$\sqrt{n}/\epsilon^{2}$ samples (using $\log(n)$ space per sample), and run
the centralized algorithm. Whenever
$m=o\left(\sqrt{n}\log(n)/\epsilon^{2}\right)$, the memory limitation prevents
us from running the centralized algorithm. For this case we choose a different
comparison graph, inducing a tester that uses more samples:
$\Theta\left(n\log(n)/(m\epsilon^{4})\right)$.

We start by describing how to execute the collision-based tester within the
limitations of the model: we use half of the memory ($m/2$ bits) to maintain a
global collision counter, and the other half would allow us to store
$m^{\prime}$ samples at each given time, so we are able to compare all
$m^{\prime}$ samples with one another. For each batch we store all
$m^{\prime}$ samples, compare them among themselves and add to global counter,
and then delete them and clear the space for a new batch. We note that the
global counter must suffice to compute $Z$ (for the right comparison graph
$G$), and $T$ can be easily computed beforehand (knowing $m,\tau$, and $s$ –
the number of samples to be used). This is indeed enough to execute the
collision-based algorithm $(G,\tau)$.

As with the previous model, we again use a simple observation regarding the
model:

######  Observation 2.

In order to execute a collision-based algorithm $(G,\tau)$ in the streaming
model, it suffices to allocate $\log\left(T\right)$ bits of memory for the
global collision counter. This is true as once the global collision counter
reaches the value $T$, the tester can immediately terminate and reject.

We now need to choose the correct size of each batches. We use the disjoint
cliques graph, this time with parameter $m^{\prime}$ for the size of each
clique. The total number of samples (and our complexity measure) is
$q=\left|V\right|$, and we write for the number of cliques $\ell=q/m^{\prime}$
(for simplicity we assume $\ell$ is an integer). Using Corollary 3.3, with the
values of $m^{\prime},\ell$, our condition is:

$m^{\prime}\sqrt{q/m^{\prime}}\geq\frac{35\sqrt{n}}{\epsilon^{2}},$

and choosing $q,m^{\prime}$ to make it an equality, after simplifying we get
that

$q=\frac{3000n\log(n)}{m\epsilon^{4}}$

are enough samples.

Note that the tester is defined only when
$1\leq\ell=q/m^{\prime}=2\log(n)\sqrt{3000n}/\left(m\epsilon^{2}\right)$,
which is equivalent to $m\leq 2\log(n)\sqrt{3000n}/\epsilon^{2}$. This
complies with the fact that larger $m$ already allows us to use the
centralized tester.

Taking the minimal required number of samples gives us a comparison graph with
$\left|E\right|=\Theta\left(n/\epsilon^{4}\right)$, which in turn dictates a
threshold $T=\Theta\left(1/\epsilon^{4}\right)$. Using the observation, we
must have $m/2\geq\log\left(T\right)$, which translates to
$m=\Omega\left(\log(1/\epsilon)\right)$. We also require that $m^{\prime}\geq
3$ (a prerequisite of Corollary 3.3, even though we can also make it work for
$m^{\prime}=2$), overall implying correctness whenever
$m\geq\Theta\left(\max\left\\{\log(1/\epsilon),\log n\right\\}\right)$.

The corollary shows a tester for a wide range of $m$ (extending the range
achieved in [13]). We are still left with the restriction of
$m=\Omega\left(\max\left\\{\log(1/\epsilon),\log n\right\\}\right)$, which
essentially comes from our need to count collisions and to be able to store at
least $2$ full samples at the same time.

We leave open an interesting question posed also in [13]: is it possible to
test for uniformity in the scarce regime, and if so – what is the sample
complexity required to do so? (The scarce regime is essentially
$m=o\left(\log(n)\right)$. Though, to comply with our result - e.g., for
absurdly small values of $\epsilon$ \- it can be redefined to
$m=o\left(\max\left\\{\log(1/\epsilon),\log n\right\\}\right)$ )

####  3.2.2 Simultaneous Model with Memory Constraints

The main difficulty in this section seems to be handling the multiple
parameters: on top of $n,\epsilon$ that define the testing problem, we now
deal with $k$ processors only able to communicate a short message to the
referee. Each of which can store at most $m$ bits of memory (or $m^{\prime}$
samples, as before) in order to process its inputs and compute its message.

######  Corollary 3.15.

In the memory-constrained simultaneous model, whenever
$m=\Omega\left(\log(1/\epsilon)\right)$ bits of memory are allowed for each
player, and $\log\left(1/\epsilon^{4}\right)$ bits of communication are
allowed for each player, uniformity can be tested using

$\Theta\left(\frac{n}{k\epsilon^{4}}\cdot\max\left\\{\frac{\log(n)}{m},\frac{\sqrt{k}\epsilon^{2}}{\sqrt{n}}\right\\}\right)$

samples per player.

Note that in the regime of very small memory constraint, the problem suddenly
"parallelize" perfectly: imagine taking
$k\leq\Theta\left((n/\epsilon^{4})\cdot(\log^{2}(n)/m^{2})\right)$ machines
with memory $m$ per machine. In this case, each machine needs only a $1/k$
fraction of the amount of samples required for a single machine with memory
$m$. This is true as the real barrier here is the overall storage, which
indeed grows linearly in the number of machines used.

######  Proof 3.16.

We first note that if $m^{\prime}\geq c\sqrt{n/(k\epsilon^{4})}$, for the
constant $c$ of the prove in Corollary 3.7, then each player can store all the
samples she needs, and therefore $\Theta\left(\sqrt{n/(k\epsilon^{4})}\right)$
samples per player are enough.

Next, we show the required adjustments whenever
$m^{\prime}<c\sqrt{n/(k\epsilon^{4})}$.777Whenever
$m^{\prime}=\Theta(\sqrt{n/(k\epsilon^{4})})$, these adjustments are required,
but the asymptotic sample complexity is similar to the case of having enough
memory. In this case, the two terms in the maximum function have the same
asymptotic value.

Under this regime, the number of samples we are able to store limits us. As we
have $k$ simultaneous players, our graph can be written as
$G=\bigsqcup_{i}G_{i}$, where $G_{i}$ is the graph of the player $i$. Only
now, each $G_{i}$ should be adjusted to the memory constraint, and this can be
done as before, by dividing each $G_{i}$ to disjoint cliques, meaning
$G_{i}=\bigsqcup_{j}G_{ij}$, where each $G_{ij}$ is isomorphic to
$K_{m^{\prime}}$.

The execution of $(G,\tau)$ then can be done, relying on previous
observations: each players uses half her space $m/2$ to calculate the value
$Z_{i}$ (or a special signal for the case $Z_{i}>T$). She then sends these
bits to the referee, using $\log(T)$ bits of communication. This can be done
as long as $m=\Omega\left(\log(T)\right)$.

To calculate the sample complexity (per player), we use $q=\left|V\right|$ for
the total amount of samples and note that our entire graph is a set of
$\ell=q/m^{\prime}$ disjoint cliques of size $m^{\prime}$ each. Using
Corollary 3.3, we know the algorithm successfully tests for uniformity
whenever

$m^{\prime}\sqrt{q/m^{\prime}}=\Omega\left(\sqrt{n}/\epsilon^{2}\right).$

And after simplifying, and choosing the minimal $q$, we get a tester with

$q=\Theta\left(\frac{n\log(n)}{m\epsilon^{4}}\right).$

We do note, however, that $q$ is the total amount of samples, not our
complexity measure. But using symmetry, it means that each player uses

$\Theta\left(\frac{n\log(n)}{mk\epsilon^{4}}\right)$

samples.

We finish by noting again that in our comparison graph we have
$\left|E\right|=\Theta\left(n/\epsilon^{4}\right)$, which means
$T=O\left(1/\epsilon\right)$, and so the communication and memory constraints
are as in previous sections: we must have
$m=\Omega\left(\log(1/\epsilon)\right)$ bit of memory per player, and each
player sends only $O\left(\log(1/\epsilon)\right)$ bits to the referee.

###  3.3 The CONGEST Model

####  3.3.1 Problem Definition

In the CONGEST model, players can communicate over private peer-to-peer
channels (communication edges), and the process is divided to rounds. Each
round allows $O\left(\log n+\log k\right)$ bits of communication on each
channel (intuitively, allowing to send a constant amount of input tokens, or
node identifiers). The complexity measure is the number of communication
rounds needed to solve a problem, as the algorithm tries to avoid congestions
(the case where a large amount of information is destined to go through a
specific communication edge).

The output of model is YES if no player raised a flag, and NO is at least one
player did so. This can be defined similarly for the testing problem. However,
using extra $D$ rounds (where $D$ is the diameter of the communication graph)
- the task is equivalent to having one player output the answer. As we do not
aim for less than $O(D)$ rounds, we relax and present the following CONGEST
version of uniformity testing (which is similar to the one in [17]):

We have a communication graph with $k$ processors, each holds exactly one
sample from the distribution $P$. We only consider the case of having enough
samples throughout the whole graph (meaning $k=\Omega(\sqrt{n}/\epsilon^{2})$,
as otherwise the task is impossible). An $\epsilon$-uniformity tester is a
communication procedure that ends where one player outputs a single bit $b$,
such that:

  1. 1.

If $P=U_{n}$, then $b=1$ with probability at least $2/3$.

  2. 2.

If $P$ is $\epsilon$-far from uniform, then $b=0$ with probability at least
$2/3$.

The complexity of the algorithm is measured by the number of communication
rounds needed to channel enough information to one node.

####  3.3.2 An Improved Algorithm

In [17], a tester for this task was given with round complexity of
$O(D+n/(k\epsilon^{4})$ rounds. We revisit this algorithm and show that
certain communication graphs are good for testing. In these graphs, the
players can: (1)detect the graph is good within $O(D)$ rounds; (2)shave the
factor of $O(n/(k\epsilon^{4}))$ rounds, by using a different testing routine,
hence solve the testing problem within $O(D)$ rounds. Hence, without hurting
the round complexity on a general graph, we get better round complexity
whenever the graph is “good” (without having prior knowledge that this is the
case).

We next give a sketch of the algorithm, and a proof of its correctness. The
idea behind this algorithm is gathering sets of samples in a small amount of
“important” nodes that are well-connected. These nodes would then simulate
virtual nodes, each having a decent-sized set of samples (one node might
simulate more than one virtual node). We then let each virtual node run a
testing procedure of the simultaneous case, and collect the answers to
aggregate them at one need, acting as the referee of the simultaneous model.

The details are as follows:

  1. 1.

The players identify the player with the largest identifier, node $r$, and
construct a BFS tree $T$ rooted at $r$. This can be done using $O(D)$ rounds.

  2. 2.

The players cunningly pipeline samples up the tree to collect them in bundles
of $s$ samples: first they count the amount of samples in each subtree, and
then they only pipeline the remainders, each player $i$ keeping $b_{i}\cdot s$
samples for himself, where $b_{i}$ is an integer – the amount of bundles. The
pipelining takes $O(D+s)$ rounds.

  3. 3.

Each player with $b_{i}>0$ simulates for each of his $b_{i}$ bundles a virtual
node running on this sample set. Each such simulation is done independently.
This part takes no communication at all.

  4. 4.

The players propagate the answers of simulations up the tree (as the answers
are cheap in communication), and once all of these have reached the root $r$,
it simulates the referees and outputs the answer. This takes another $O(D)$
rounds.

We note that optimizing over the bundle size $s$ gives us
$s=n/(k\epsilon^{4})$, which can potentially be much larger than $D$, in which
case the bottleneck of the algorithm is pipelining the samples up the tree.

We now turn to think of the communication graph as a potential comparison
graph. Indeed, each node starts with a single sample, and comparing two
samples of neighboring nodes takes a single round. Thus, it is a local
process, which is very cheap in round complexity, and use communication over
all channels. To this end, we suggest the following two procedures:

###### Detection procedure.

In order to detect that our communication graph is a good comparison graph,
one needs to have the values $\left|E\right|,c(G)$. We use $d_{i}$ for the
degree of node $i$. We then have:

$\displaystyle\left|E\right|$ $\displaystyle=(1/2)\sum_{i}d_{i}$
$\displaystyle c(G)$ $\displaystyle=\sum_{i}\binom{d_{i}}{2}$

These sizes are also bounded by $k^{2}$ and $k^{3}$ (where $k=\left|V\right|$
is both the number of nodes, and the number of samples). This means that we
can use messages of $O\left(\log(k)\right)$ bits to perform the summation up
the tree, and using $O(D)$ rounds of communication, the root $r$ knows both
these values, as well as $n,\epsilon$, and it can determine whether the
communication graph works for some threshold value $\tau_{0}$. well as a
comparison graph. It takes another $O(D)$ to propagates the answer to all
nodes.

###### Alternative testing.

In the case of a positive detection, we use a _single_ round for each player
to send its sample to every neighbor with a larger identifier.888This is not
crucial. If we do not have order on the vertices, they can each send all of
their neighbors, and each comparison will be done exactly twice Next, each
player locally counts the number of collisions it had with its neighbors
$Z_{i}$ (no communication needed), and we note that the total amount of
collisions is $Z=\sum_{i}Z_{i}$. As $Z$ is bounded by the number of
comparisons (edges), we know that all partial sums of values $Z_{i}$ can be
expressed using $O\left(\log(k)\right)$ bits. Thus, we can use an extra $O(D)$
rounds to sum the number of collisions up the tree. As the root can also
calculate $T$, we actually get a simulation of the collision tester , where
$G$ is the communication graph.

To sum up, both the detection, and the alternative testing can be done in
$O(D)$ rounds, which means that for any network that has a good topology
(depending on $n,\epsilon$ and the choice of $\tau$) – the players can solve
uniformity using $O(D)$ rounds.

####  3.3.3 Discussion

The improvement above shows how to connect an interactive model to the
framework of collision-testers in a non-trivial way. However, in this
implementation only extremely local comparisons were made: ones that takes $1$
round to perform.

One can generalize this idea using comparison of higher constant order, $t$
(namely, all samples that are of distance $t$ from one another). This would
mean taking the graph $G^{t}$ as our comparison graph. This graph has more
edges, and is therefore should be a better fit.999As it turns out, not every
comparison necessarily helps, but usually adding comparisons does help Indeed,
one should modify the detection process: we will need to calculate
$\left|E(G^{t})\right|,C(G^{t})$ up the tree, and each node would have to make
sure its $t$-environment is no too large, as to not create a local congestion
(as such congestions can occur even in a constant-diameter neighborhood). If
the detection process passes, the $t$-local comparisons can be made for any
constant parameter $t$. We expect larger value of $t$ to work for a broader
family of graphs (for example, whenever $G$ is merely connected, the graph
$G^{k}$ is the $k$-sized clique, which is known to be a good tester for large
enough $k$)

We conclude with this: one can use $O(D)$ rounds to try detecting the local
testability of the graph $G^{t}$, for any constant $t$. Depending on further
assumptions, one can conduct a smart search of a locality parameter $t$
(trying different values along the way), especially whenever
$n/(k\epsilon^{4})$ is much larger than the diameter $D$, and we wish to avoid
the global pipelining procedure.

###  3.4 Testing Identity to a Fixed Distribution

For the classic model, it was shown in [16, 20] that uniformity testing is
complete with respect to testing identity to a fixed distribution, $D$.
Specifically, the black-box reduction in [20] uses a random filter $F_{D}$
which we can apply on our sample set to obtain a new one. This is done in a
way that every sample from $D$ becomes a uniform sample (on a slightly larger
domain, $[m]$), and similarly a sample from any distribution that is
$\epsilon$-far from $D$, becomes a sample from some a distribution that is
$\epsilon^{\prime}$-far from uniform (on $[m]$). The trick is the existence of
such a filter with $m=\Theta(n)$ and $\epsilon^{\prime}=\Theta(\epsilon)$,
which roughly maintains the sample complexity.

We note that the same reduction applies for all of the results above. Indeed,
in all of them every node (or sample) in is known at first to a single
processor (the one who draws the sample). Thus, all processors can run the
same global filter $F_{D}$ that only depends on $D$ (we assume here they are
know the goal of the protocol, and the distribution $D$ we are testing for).

Formally, each node $v$ is originally associated with a sample $S_{P}(v)$, and
a processor that holds this sample. Running it through the filter, we get a
fresh sample $F_{D}(S_{D}(v))$ on which we run the rest of testing procedure.
Overall, the nodes of our graph $G$ are now associated with $\left|V\right|$
samples that are either from uniform distribution (on $[m]$) or on an
$\epsilon^{\prime}$-far distribution, and from here we can use a collision-
based uniformity testing.

##  4 Proof of the Structural Theorem

We now prove our structural theorem, as well as the more specific lemma for
the disjoint cliques graph.

###  4.1 Proof of Theorem 3.1

The outline for the proof follows an outline similar to the one of [15]. Our
main challenge is to fit the proof for _any_ comparison graph, rather than a
specific one – that of a full clique – which describes the classic centralized
uniformity tester.

By doing so, we get not one, but _three_ separate conditions on the
_comparison graph_ that together guarantee that it can be used to plan an
$(n,\epsilon)$-uniformity tester. This supplies a better, multi-dimensional
understanding of how well a collision-based algorithm is guaranteed to
perform. We note that if one is willing to ignore constants, one could simply
fix $\tau=1/2$ and combine the first two conditions into one. _However_ , a
side goals of ours is to optimize the analysis for both known results and our
new ones, and for that goal we leave $3$ different conditions and optimize
over $\tau$ to show that putting the threshold right in the model does not
give the best complexity guarantee. We are then left with the following
formulation:

  * Theorem 3.1

Fix a domain size $n$ and a proximity parameter $\epsilon$. If the following
hold for an algorithm :

    1. 1.

$\left|E\right|\geq\frac{4n}{\tau^{2}\cdot\epsilon^{4}}$,

    2. 2.

$\left|E\right|\geq\frac{16n}{(1-\tau)^{2}\cdot\epsilon^{4}}$, and

    3. 3.

$\frac{c(G)}{\left|E\right|^{2}}\leq\frac{(1-\tau)^{2}\epsilon^{2}}{16\sqrt{n}}$,

then is an $\epsilon$-uniformity tester.

To prove our theorem, we first need to understand how the tester works. The
goal of a collision-based tester is to estimate $\mu$ well enough to
distinguish between the YES and NO cases. The reason such testers work is
because for the uniform distribution $U_{n}$, we have
$\mu_{{}_{U_{n}}}=\frac{1}{n}$, and for any $\epsilon$-far distribution $P$,
one can easily show that $\mu_{P}\geq\frac{1+\epsilon^{2}}{n}$. This means
that $\mathbb{E}[Z]$ is noticeably different when fed samples from a YES case
and when samples are drawn from a NO case. Therefore, our first proposition is
that:

######  Proposition 4.1.

Fix an algorithm , and an input distribution $P\in\Delta([n])$. We have

$\mathbb{E}[Z]=\left|E\right|\cdot\mu.$

######  Proof 4.2.

For each comparison edge $(u,v)=e\in E$, we have
$\mathbb{E}[\mathds{1}_{e}]=\Pr_{S}[S(u)=S(v)]=\mu$, the probability of a
collision when taking two samples. Thus:

$\mathbb{E}[Z]=\mathbb{E}[\sum_{e\in E}\mathds{1}_{e}]=\sum_{e\in
E}\mathbb{E}[\mathds{1}_{e}]=\sum_{e\in E}\mu=\left|E\right|\cdot\mu.$

As per usual, the next step is to bound the variance of the random variable
$Z$ in order to later show concentration to some degree in both YES and NO
cases. The bound we get consists of two separate terms. The first term can be
though of as an unavoidable, inherent variance that comes along with each and
every comparison. However, the second term is more tricky, and it is created
and described by the dependencies between different comparisons. For example,
in the case where all comparisons are done on freshly drawn pairs of samples,
all comparisons are completely independent and indeed the comparison graph – a
perfect matching – has $c(G)=0$ which cancels the second term completely.

######  Lemma 4.3.

Fix an algorithm , and an input distribution $P\in\Delta([n])$. then

$\operatorname*{Var}[Z]=\left|E\right|\cdot(\mu-\mu^{2})+c(G)\cdot(\gamma-\mu^{2}).$

######  Proof 4.4.

By definition, $Z=\sum_{e\in E}\mathds{1}_{e}$, and so

$\mathbb{E}[Z^{2}]=\mathbb{E}\left[\left(\sum_{e\in
E}\mathds{1}_{e}\right)^{2}\right]=\mathbb{E}\left[\sum_{\begin{subarray}{c}e_{1}\in
E\\\ e_{2}\in
E\end{subarray}}\mathds{1}_{e_{1}}\cdot\mathds{1}_{e_{2}}\right]=\sum_{\begin{subarray}{c}e_{1}\in
E\\\ e_{2}\in
E\end{subarray}}\mathbb{E}[\mathds{1}_{e_{1}}\cdot\mathds{1}_{e_{2}}].$

This sum consists of $\left|E\right|^{2}$ summands. We break these into 3
types of summands:

  * •

$\left|e_{1}\cup e_{2}\right|=2$, which means $e_{1}=e_{2}$. In this case the
summand is simply

$\mathbb{E}[\mathds{1}_{e_{1}}^{2}]=\mathbb{E}[\mathds{1}_{e_{1}}]=\mu.$

  * •

$\left|e_{1}\cup e_{2}\right|=3$. i.e., we have a common vertex. We call the 3
vertices $u,v,w$, and calculate:

$\mathbb{E}\left[\mathds{1}_{e_{1}}\cdot\mathds{1}_{e_{2}}\right]=\mathbb{E}\left[\mathds{1}_{S(u)=S(v)=S(w)}\right]=\gamma.$

  * •

$\left|e_{1}\cup e_{2}\right|=4$. In this case we have 4 distinct vertices,
and so the two indicators $\mathds{1}_{e_{1}},\mathds{1}_{e_{2}}$ are
independent, and we have

$\mathbb{E}[\mathds{1}_{e_{1}}\cdot\mathds{1}_{e_{2}}]=\mathbb{E}[\mathds{1}_{e_{1}}]\cdot\mathbb{E}[\mathds{1}_{e_{2}}]=\mu^{2}.$

There are exactly $\left|E\right|$ summands of the first type. Each summand of
the second type corresponds uniquely to a directed $2$-paths in $G$, the one
that consists of $e_{1},e_{2}$. As our entire sum goes we over all (ordered)
pairs of edges, we must include all directed $2$-paths, and so we have exactly
$c(G)$ summands of this type.101010As this might be confusing, we note that
both pairs $e_{1},e_{2}$ and $e_{2},e_{1}$ appear in our sum, and indeed each
one of them corresponds to a different directed $2$-path The rest of the
summands must be of the third type, and their number amounts to
$\left|E\right|^{2}-\left|E\right|-c(G)$.

Putting it all together, we have

$\displaystyle\mathbb{E}[Z^{2}]$
$\displaystyle=\left|E\right|\cdot\mu+c(G)\cdot\gamma+(\left|E\right|^{2}-\left|E\right|-c(G))\cdot\mu^{2}$
$\displaystyle=\left|E\right|^{2}\cdot\mu^{2}+\left|E\right|\cdot(\mu-\mu^{2})+c(G)\cdot(\gamma-\mu^{2}).$

We now use Proposition4.1 to see that
$\mathbb{E}[Z]^{2}=\left|E\right|^{2}\cdot\mu^{2}$. Plugging this in, we get:

$\operatorname*{Var}[Z]=\mathbb{E}[Z^{2}]-\mathbb{E}[Z]^{2}=\left|E\right|\cdot(\mu-\mu^{2})+c(G)\cdot(\gamma-\mu^{2}),$

Which finishes the proof.

It is interesting that to accurately express the expectation and variance of
$Z$, it is enough to sum up the whole graph $G$ with only two quantified
values, and even a bit surprising that $\left|V\right|$ is not even one of
them (though, we later show in Section 5.1, that there is an indirect
connection).

We now wish to show that any collision-based tester that has certain
properties can test uniformity well. After fixing the tester, we partition the
proof into three cases according to the input distribution being tested, and
show that in each case the tester indeed errs with probability at most $1/4$.

We first give a specific application of Chebyshev’s inequality, one that will
be used in _all_ three cases to follow:

######  Lemma 4.5.

Fix an algorithm , and an input distribution $P\in\Delta([n])$. If

$4\operatorname*{Var}[Z]\leq\left|E\right|^{2}\cdot\left(\frac{1+\tau\epsilon^{2}}{n}-\mu\right)^{2}$
(1)

then errs on the distribution $P$ with probability at most $1/4$.

######  Proof 4.6.

Using simpler notations, the r.h.s of (1) equals to
$\left(\left|E\right|\cdot\frac{1+\tau\epsilon^{2}}{n}-\left|E\right|\cdot\mu\right)^{2}=(T-\mathbb{E}[Z])^{2}$,
which means (1) can be written as:

$4\operatorname*{Var}[Z]\leq(T-\mathbb{E}[Z])^{2}.$

We also note that since $\tau\in[0,1]$, the threshold is right in between the
value of $\mathbb{E}[Z]$ for the YES case (which corresponds to $\tau=0$), and
the value of $\mathbb{E}[Z]$ for _any_ NO case (which can be as low as the
value corresponding to $\tau=1$).

Now, looking at events over the probability space of the sampling process, one
can see that every time the tester errs, it means the value $Z$ “fell” on the
wrong side of the threshold, which means $T$ lies in between $Z$ and
$\mathbb{E}[Z]$. Formally, it means that whenever fails,
$\left|Z-\mathbb{E}[Z]\right|\geq\left|T-\mathbb{E}[Z]\right|$. So the last
event’s probability is larger then the former’s:

$\Pr[$

Where for the second and third inequalities we used Chebyshev’s inequality,
and (1).

Equipped with Lemma 4.5, we are ready to find a sufficient condition for the
tester to succeed with high probability in each of the three cases. The first
type will simply be the YES case where $P=U_{n}$.

######  Lemma 4.7 (Uniform distribution).

Fix an algorithm , and fix $P=U_{n}$. If

$\left|E\right|\geq\frac{4(n-1)}{\tau^{2}\epsilon^{4}}$ (2)

then fails on $P$ with probability at most $1/4$.

######  Proof 4.8.

For the uniform distribution we have $\mu=1/n$, and $\gamma=1/n^{2}$. And so
using 4.3:

$\operatorname*{Var}[Z]=\left|E\right|\cdot(1/n-1/n^{2})+c(G)\cdot(1/n^{2}-1/n^{2})=\left|E\right|\cdot\left(\frac{n-1}{n^{2}}\right).$

Using Lemma 4.5, we see that for the algorithm to work well on the uniform
distribution, it is enough to require:

$4\left|E\right|\cdot\left(\frac{n-1}{n^{2}}\right)\leq\left|E\right|^{2}\cdot\left(\frac{\tau\epsilon^{2}}{n}\right)^{2},$

which after re-arranging is equivalent to equation (2).

We now turn to the two other cases. We split the set of $\epsilon$-far
distributions into two, according to the dominant summand in the variance of
$Z$ after fixing a tester . Formally, we define

$\mathcal{P}_{1}($ $\mathcal{P}_{2}($

The two “types” together cover every $\epsilon$-far distribution (no matter
what was chosen). We first show that both summands in the variance are non-
negative, since the two terms $\mu-\mu^{2}$ and $\gamma-\mu^{2}$ are non-
negative for any distribution $P$.

Indeed, for the first term we use the common fact that $\frac{1}{n}\leq\mu\leq
1$, and so $\mu-\mu^{2}=\mu(1-\mu)\geq 0$.

For the second, we use Cauchy-Schwarz inequality:

$\mu^{2}=\left(\sum_{i=1}^{n}P_{i}^{2}\right)^{2}=\left(\sum_{i=1}^{n}P_{i}^{0.5}\cdot
P_{i}^{1.5}\right)^{2}\leq\sum_{i=1}^{n}P_{i}\cdot\sum_{i=1}^{n}P_{i}^{3}=\gamma.$

Now, once a tester is fixed, we have the two lemmas that follow, each deals
with one of the two distributions families induced by the algorithm.

######  Lemma 4.9 (Distributions from $\mathcal{P}_{1}($).

Fix an algorithm , and an $\epsilon$-far distribution $P\in\mathcal{P}_{1}($.
If

$\left|E\right|\geq\frac{16n}{(1-\tau)^{2}\epsilon^{4}},$

then fails on $P$ with probability at most $1/4$.

######  Proof 4.10.

Since $P\in\mathcal{P}_{1}($, we know that $4\operatorname*{Var}[Z]\leq
8\left|E\right|\cdot(\mu-\mu^{2})\leq 8\left|E\right|\cdot\mu$.

Therefore, to satisfy (1), it suffice to require

$8\left|E\right|\cdot\mu\leq\left|E\right|^{2}\cdot\left(\frac{1+\tau\epsilon^{2}}{n}-\mu\right)^{2}.$

Let $\alpha$ be such that $\mu=\frac{1+\alpha}{n}$. Since $P$ is
$\epsilon$-far from uniform, we know that $\alpha\geq\epsilon^{2}$. Using this
notation, we have

$8\left|E\right|\cdot\left(\frac{1+\alpha}{n}\right)\leq\left|E\right|^{2}\cdot\left(\frac{1+\tau\epsilon^{2}}{n}-\frac{1+\alpha}{n}\right)^{2},$

and after re-arranging, we get

$\left|E\right|\geq\frac{8(1+\alpha)n}{(\tau\epsilon^{2}-\alpha)^{2}}.$

As this must be true for _any_ value of $\alpha$, we show that it is enough to
require that it holds for $\alpha=\epsilon^{2}$.

In order to show this, we think of $f(\alpha)=8n(1+\alpha)$, $\ \
g(\alpha)=\tau\epsilon^{2}-\alpha$, and so

$\left(\frac{f}{g^{2}}\right)^{\prime}=\frac{8n(1+\alpha)^{\prime}\cdot
g^{2}(\alpha)-8n\cdot
2g(\alpha)}{g^{4}(\alpha)}=\frac{8n}{g^{4}(\alpha)}\cdot(1+\alpha-2g(\alpha))\cdot
g(\alpha).$

But the term $8n/g^{4}(\alpha)$ is positive, and whenever
$\alpha\geq\epsilon^{2}$ (and since $\tau\leq 1$), we also have it that
$g(\alpha)\leq 0$ as well as $(1+\alpha-2g(\alpha)\geq 0$. To conclude, for
the range $\alpha\geq\epsilon^{2}$, we have that $(f/g^{2})^{\prime}\leq 0$,
which means the maximum of the function $(f/g^{2})$ in exactly when
$\alpha=\epsilon^{2}$.

A sufficient condition, then, for (1) to hold (and subsequently, for to err on
$P$ with probability at most $1/4$) is

$\left|E\right|\geq\frac{16n}{(1-\tau)^{2}\epsilon^{4}},$

which ends the proof.

######  Lemma 4.11 (Distributions from $\mathcal{P}_{2}($).

Fix an algorithm , and fix an $\epsilon$-far distribution
$P\in\mathcal{P}_{2}($. If

$c(G)\leq\frac{\left|E\right|^{2}(1-\tau)^{2}\epsilon^{2}}{16\sqrt{n}},$

then fails on $P$ with probability at most $1/4$.

######  Proof 4.12.

We again want to show that given our premise, inequality (1) holds.

We start with a finer analysis of $\gamma-\mu^{2}$. For this purpose, we
define the $n$ dimensional vector $a:=P-U_{n}$, which means $a_{i}=P_{i}-1/n$.
We thus have $\sum_{i=1}^{n}a_{i}=0$. Now, we compute:

$\displaystyle\gamma-\mu^{2}$
$\displaystyle=\sum_{i=1}^{n}(1/n+a_{i})^{3}-\left[\sum_{i=1}^{n}(1/n+a_{i})^{2}\right]^{2}$
$\displaystyle=\left(\sum_{i=1}^{n}1/n^{3}+3\sum_{i=1}^{n}a_{i}/n^{2}+3\sum_{i=1}^{n}a_{i}^{2}/n+\sum_{i=1}^{n}a_{i}^{3}\right)$
$\displaystyle-\left(\sum_{i=1}^{n}1/n^{2}+2\sum_{i=1}^{n}a_{i}/n+\sum_{i=1}^{n}a_{i}^{2}\right)^{2}$
$\displaystyle=\left(1/n^{2}+0+(3/n)\left\|a\right\|_{2}^{2}+\left\|a\right\|_{3}^{3}\right)-\left(1/n+0+\left\|a\right\|_{2}^{2}\right)^{2}$
$\displaystyle=\left(1/n^{2}+(3/n)\left\|a\right\|_{2}^{2}+\left\|a\right\|_{3}^{3}\right)-\left(1/n^{2}+(2/n)\left\|a\right\|_{2}^{2}+\left\|a\right\|_{2}^{4}\right)$
$\displaystyle=\left\|a\right\|_{2}^{2}/n+\left\|a\right\|_{3}^{3}-\left\|a\right\|_{2}^{4}$
$\displaystyle\leq\left\|a\right\|_{2}^{2}/n+\left\|a\right\|_{2}^{3}$

In the last step we used the fact
$\left\|\cdot\right\|_{3}\leq\left\|\cdot\right\|_{2}$, and omitted the last
term. We now again denote $\mu=\frac{1+\alpha}{n}$, so that
$\left\|a\right\|_{2}^{2}=\alpha/n$. Combining the above with Lemma 4.3, and
the assumption on $P$, we can upper-bound the variance:

$4\operatorname*{Var}[Z]\leq 8c(G)\cdot(\gamma-\mu^{2})\leq
8c(G)\cdot\left(\frac{\alpha}{n^{2}}+\frac{\alpha^{1/5}}{n^{1.5}}\right)=8c(G)\cdot\left(\frac{1}{\alpha}+\frac{\sqrt{n}}{\sqrt{\alpha}}\right)\frac{\alpha^{2}}{n^{2}}$
(3)

The premise we have is equivalent to:

$\frac{\left|E\right|^{2}}{c(G)}\geq\frac{16\sqrt{n}}{(1-\tau)^{2}\epsilon^{2}}=\frac{8}{(1-\tau)^{2}}\cdot\left(\frac{\sqrt{n}}{\epsilon^{2}}+\frac{\sqrt{n}}{\epsilon^{2}}\right),$

and using $\sqrt{n}\geq 1$ and $\epsilon^{2}\leq\alpha$, as well as
$\epsilon^{2}\leq\epsilon\leq\sqrt{\alpha}$, we deduce:

$\frac{\left|E\right|^{2}}{c(G)}\geq\frac{8}{(1-\tau)^{2}}\cdot\left(\frac{1}{\alpha}+\frac{\sqrt{n}}{\sqrt{\alpha}}\right),$

which, after re-arranging, is equivalent to

$8c(G)\cdot\left(\frac{1}{\alpha}+\frac{\sqrt{n}}{\sqrt{\alpha}}\right)\leq\left|E\right|^{2}(1-\tau)^{2}.$

Combined with inequality (3) which bounds the variance, we have:

$4\operatorname*{Var}[Z]\leq\left|E\right|^{2}\frac{(1-\tau)^{2}\alpha^{2}}{n^{2}}.$

We again use the fact $\alpha\geq\epsilon^{2}$ to deduce that
$(1-\tau)\alpha=\alpha-\tau\alpha\leq\alpha-\tau\epsilon^{2}$. Now we can
conclude:

$4\operatorname*{Var}[Z]\leq\left|E\right|^{2}\left(\frac{(1-\tau)\alpha}{n}\right)^{2}\leq\left|E\right|^{2}\cdot\left(\frac{\alpha-\tau\epsilon^{2}}{n}\right)^{2}=\left|E\right|^{2}\cdot\left(\frac{1+\tau\epsilon^{2}}{n}-\mu\right)^{2},$

Which means that indeed (1) holds, and thus by applying 4.5, the tester errs
on samples from $P$ with probability at most $1/4$.

The proof of Theorem 3.1 then follows from the last three lemmas. Once the
tester is fixed, each of the three conditions guarantees correctness (w.p at
least $3/4$) on $P=U_{n}$, $P\in\mathcal{P}_{1}($ and $P\in\mathcal{P}_{2}($,
respectively.

###  4.2 Proof of Lemma 3.2

We re-formulate the lemma for the disjoint cliques graph, now followed by a
formal proof.

  * Lemma 3.2

Fix $n,\epsilon$. Fix a comparison graph $G=\bigsqcup_{i=1}^{\ell}G_{i}$,
where each $G_{i}$ is isomorphic to $K_{q}$, for some $q\geq 3$. If the
following hold for an algorithm :

    1. 1.

$q\sqrt{\ell}\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\epsilon^{2}}$

    2. 2.

$q\sqrt{\ell}\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\epsilon^{2}}$

    3. 3.

$q\ell\geq\frac{24\sqrt{n}}{(1-\tau)^{2}\epsilon^{2}}$

then is an $\epsilon$-uniformity tester that uses $\left|V\right|$ samples.

######  Proof 4.13.

We wish to show the three conditions of Theorem 3.1 can be relaxed using the
structure of the graph. It is enough to show a lower bound on
$\left|E\right|$, and an upper bound on $c(G)$, which indeed can be done.
Whenever $q\geq 3$, we have:

$\displaystyle\left|E\right|$
$\displaystyle=\ell\cdot\frac{1^{2}-1}{2}\geq\frac{\ell\cdot q^{2}}{3}$
$\displaystyle c(G)$ $\displaystyle=\ell\cdot\binom{q}{3}\leq\frac{\ell\cdot
q^{3}}{6}$

And so

$\frac{\left|E\right|^{2}}{c(G)}\geq\frac{\ell^{2}q^{4}/9}{\ell
q^{3}/6}=\frac{2\ell q}{3}.$

Which means that we can replace the premise in the main theorem with a the new
form:

  1. 1.

$q\sqrt{\ell}\geq\frac{\sqrt{12}\sqrt{n}}{\tau\cdot\epsilon^{2}}$

  2. 2.

$q\sqrt{\ell}\geq\frac{\sqrt{48}\sqrt{n}}{(1-\tau)\cdot\epsilon^{2}}$

  3. 3.

$q\ell\geq\frac{24\sqrt{n}}{(1-\tau)^{2}\epsilon^{2}}$

##  5 Limitations of the Method

In this section our goal is to better understand the possibilities (and
impossibilities) of collision-based testing, in comparison to arbitrary
testing methods (many of which were developed for specific testing task, as
mentioned earlier in the text).

Here, we use Definition 2.2 to shift the discussion to graph terminology,
focusing on the comparison graph. We leverage simple graph properties to show
some limitations that apply when generating testers, such as done in Section
3.

The results hereinafter apply to testers that can be proven to work using our
structural theorem. However, we formulate a simple conjecture (regarding the
minimal number of comparisons required for any tester) that implies similar
results for any tester that answers Definition 2.2. In matter of fact, we will
formally show that the comparison graphs we have chosen before are essentially
the best that could have been chosen for their respective models. If the
conjecture is true, this would imply all of these testers are optimal with
respect to any tester from Definition 2.2).

We emphasize that in some models, previous works already show tight (or near-
tight) lower bounds for arbitrary testers. Interestingly enough, our optimal
collision-based testers achieve optimal (or near-optimal) results even if one
is allowed to use an arbitrary method. Thus, the sample complexity we achieve
is not only optimal with respect to collision-based testing, but also near-
optimal with respect to any uniformity tester. This is evident from a variety
of known lower bounds in some of the models considered in this paper (See [25,
16, 23, 13, 4] for these lower bounds111111More lower bounds in the
simultaneous model hold only for the case of a single sample per player, not
considered in this paper. e.g., [3, 6]). The full discussion of collision-
based testing vs. arbitrary testers appears at the end of this section, in
hope to give a clearer picture of how strong collision-based testing can be.

We first go on to show some basic inequalities that hold in any simple graph
(and in our comparison graphs as well). These will serve us for the rest of
this section. The goal is to establish the inherent connection between the $3$
sizes: $\left|V\right|,\left|E\right|,c(G)$ in any simple graph $G$.

###  5.1 Basic Graph Properties

We start by stating the following easy lemma that connects our quantities of
interest in any simple graph.

######  Lemma 5.1.

For any simple graph $G$, it holds that:

  1. 1.

$\left|E\right|\leq\frac{\left|V\right|^{2}}{2}$

  2. 2.

$\left|V\right|\geq\frac{4\left|E\right|^{2}}{2\left|E\right|+c(G)}$

  3. 3.

if $\left|V\right|\leq\left|E\right|$ then $c(G)\geq 2\left|E\right|$

Before proving the lemma, we solve a small mystery that we handled before. In
the perfect matching graph, we have a minimal amount of dependencies. In fact,
so little, that it overdoes it: it needs to take $\Theta(n/\epsilon^{4})$
samples in order to make the $\Theta(n/\epsilon^{4})$ comparisons needed to
apply our structural theorem. This is far from optimal. However, we now
understand this pathology, via the following corollary:

######  Corollary 5.2.

Whenever $\left|V\right|\leq\left|E\right|$, we have:

$\left|V\right|\cdot c(G)\geq 2\left|E\right|^{2}$

######  Proof 5.3 (Proof of Corollary 5.2).

Using items 2 and 3 of lemma 5.1, we see the following: whenever
$\left|V\right|\leq\left|E\right|$, we know $c(G)\geq 2\left|E\right|$, and
plugged in the second item:

$\left|V\right|\geq\frac{4\left|E\right|^{2}}{2\left|E\right|+c(G)}\geq\frac{4\left|E\right|^{2}}{2c(G)}=\frac{2\left|E\right|^{2}}{c(G)}$

It is now obvious form the corollary, that we have some tension: On the one
hand, we need $c(G)$ to be small enough apply Theorem 3.1. On the other hand,
we do not want $c(G)$ to be _too_ small, as this would force us to have a
large amount of samples – the value that we actually wish to minimize.

We end this section with the proof of the lemma

######  Proof 5.4.

The first item is true because the graph is simple (no loops or double-edges).

For the second item, let us denote by $d_{v}$ the degree of vertex $v$. It is
known that $2\left|E\right|=\sum_{v\in V}d_{v}$. It is also clear that the set
of 2path subgraphs can be chosen by taking the middle vertex of the 2path, and
then choosing the 2 edges of the path (the order matters). So each vertex $v$
is the middle of exactly $d_{v}(d_{v}-1)$ such 2paths, and overall we have
$c(G)=\sum_{v\in V}d_{v}^{2}-d_{v}$. We now use Cauchy-Schwarz inequality:

$(2\left|E\right|)^{2}=\left(\sum_{v\in V}d_{v}\right)^{2}\leq\
\left(\sum_{v\in V}1^{2}\right)\left(\sum_{v\in
V}d_{i}^{2}\right)=\left|V\right|\cdot(2\left|E\right|+c(G))$

which proves the second item.

For the third item, we plug the premise in the second item:

$\left|E\right|\geq\left|V\right|\geq\frac{4\left|E\right|^{2}}{2\left|E\right|+c(G)}$

which means $2\left|E\right|+c(G)\geq 4\left|E\right|$, or simply $c(G)\geq
2\left|E\right|$.

###  5.2 Conditional Impossibility Results

In order to understand the scope of possible applications of Theorem 3.1, we
stick to graph notations, and combine the $3$ different types of assertions
concerning our comparison graph:

  1. 1.

The requirements needed to apply Theorem 3.1.

  2. 2.

The basic graph properties of Lemma 5.1 and Corollary 5.2.

  3. 3.

Individual assertions that apply for the model at hand.

We note that all the results below only use the first requirement of Theorem
3.1, which asks for the total number of comparisons to be large enough. We
believe this requirement to be inherent for _any_ collision-based tester to be
able to test uniformity. We formulate this belief as the following conjecture,
which would strengthen the impossibility results of this section to be
independent of the analysis (instead of limitation of Theorem 3.1, we get a
lower bound for all collision-based testers as defined in Definition 2.2).

######  Conjecture 5.5.

Any collision-based tester sa defined in Definition 2.2 that tests for
uniformity with error $1/4$ must have

$\left|E\right|=\Omega\left(\frac{n}{\epsilon^{4}}\right)$

An argument to support this conjecture is the following: on the one hand, in
the case of no dependencies at all (meaning, a new pair of samples is used for
each comparison), the conjecture holds. This case is essentially equivalent to
another known problem: the problem of finding the bias of a coin (as mentioned
in [7]). In this problem, a coin is known to have probability of either $1/n$
or at least $(1+\epsilon^{2})/n$, and we need to minimize the number of tosses
to differ the two cases. It is known that at least
$\Theta\left(n/\epsilon^{4}\right)$ tosses are needed.

On the other hand, for the other extreme – a clique graph, having maximal
dependency – the existing lower bound for uniformity testing (say, the one in
[25]) shows that
$\left|E\right|=\Theta(\left|V\right|^{2})=\Omega(n/\epsilon^{4})$. Thus, we
believe that in every case in between the conjecture should hold as well, even
though proving it appears to be a bit tricky.

####  5.2.1 Standard Processors

##### Centralized model.

As a warm-up, we turn to the classic model, with no restrictions on the graph.
We can easily see that Conjecture 5.5 helps. Using the the first of our basic
graph properties, gives
$q=\left|V\right|\geq\sqrt{2\left|E\right|}=\Omega(\sqrt{n}/\epsilon 2)$,
which is the lower bound known to hold for any uniformity tester.121212An
interesting fact, just for the classic model, is that the third condition of
Theorem 3.1 independently implies the correct lower bound: using corollary
5.2, whenever $\left|V\right|\leq\left|E\right|$, we have
$\left|V\right|\geq\frac{2\left|E\right|^{2}}{c(G)}=\Omega\left(\frac{\sqrt{n}}{\epsilon^{2}}\right)$

##### Simultaneous model.

In the simultaneous case, the main restriction is that of each player has her
own comparison graph, as no comparisons can be made between two different
players. This leads us to the following:

######  Corollary 5.6.

Assuming Conjecture 5.5 holds, the number of samples per player of any
collision-based uniformity tester in the simultaneous model is

$q^{\prime}=\Omega\left(\frac{\sqrt{n}}{\sqrt{k}\cdot\epsilon^{2}}\right).$

######  Proof 5.7.

We start by noting that in this model, our sample complexity is the maximum
amount of samples one player draws. Formally, we write the comparison graph as
the union of $k$ disjoint parts: $G=\bigsqcup_{i\in[k]}G_{i}$, where
$G_{i}=(V_{i},E_{i})$, and so the complexity measure is simply
$q^{\prime}=max_{i\in[k]}\left|V_{i}\right|$.

We note, however, that $\left|E_{i}\right|\leq\left|V_{i}\right|^{2}/2$ for
each component $G_{i}$, and therefore:

$\left|E\right|=\sum_{i\in[k]}\left|E_{i}\right|\leq\sum_{i\in[k]}\left|V_{i}\right|^{2}/2\leq
k\cdot max_{i\in[k]}\left|V_{i}\right|^{2}/2=k\cdot q^{\prime 2}/2.$

Plugging in Conjecture 5.5, we get

$q^{\prime}\geq\sqrt{\frac{2\left|E\right|}{k}}=\Omega\left(\frac{\sqrt{n}}{\sqrt{k}\cdot\epsilon^{2}}\right),$

which ends the proof.

##### Asymmetric cost model.

The more elaborate version of the asymmetric-cost model also impose similar
limitations, where the difference comes from the generalized definition of the
complexity measure.

######  Corollary 5.8.

We observe the asymmetric-cost simultaneous model, with sampling rate vector
$(R_{1},\dots,R_{k})$. If Conjecture5.5 holds, then any collision-based
uniformity tester in this model must use sampling time of

$t=\Omega\left(\frac{\sqrt{n}}{\epsilon^{2}\left\|R\right\|_{2}}\right).$

######  Proof 5.9.

We again use $G=\bigsqcup_{i\in[k]}G_{i}$, where $G_{i}=(V_{i},E_{i})$.
However, the complexity measure is the time $t$ in which player $i$ with rate
$R_{i}$ can obtain $\left|V_{i}\right|=q_{i}=t\cdot R_{i}$ samples.

Again, using the trivial edges-vertices inequality over each component
$G_{i}$, we get

$\forall i.\ \left|E_{i}\right|\leq\left|V_{i}\right|^{2}/2=t^{2}\cdot
R_{i}^{2}/2$

and summing all together, we get

$\left|E\right|=\sum_{i\in[k]}\left|E_{i}\right|\leq\sum_{i\in[k]}t^{2}\cdot
R_{i}^{2}/2\leq t^{2}\left\|R\right\|_{2}^{2}/2.$

Joined with Conjecture 5.5, it concludes the proof

$t\geq\sqrt{\frac{2\left|E\right|}{\left\|R\right\|_{2}^{2}}}=\Omega\left(\frac{\sqrt{n}}{\epsilon^{2}\left\|R\right\|_{2}}\right).$

####  5.2.2 Memory-Constrained Processors

Here we use a slightly more sophisticated argument, to show that the memory
constraint can also be translated to graph notation. We emphasize that our
desire is to show limitations of our framework, and so we relax the model and
assume that comparisons are made on designated memory cells, in which we can
only store $m^{\prime}$ element names. In order to count collisions
_accurately_ , we cannot expect to compress this data further. For example,
$m^{\prime}=o(\sqrt{n})$ and samples are drawn from the uniform distribution
$P=U_{n}$, with $99\%$ we need to write in our memory $m^{\prime}$ different
elements, and this information cannot be compressed.

We go on to show how the memory constraint translates well:

######  Claim 1.

Let us assume a constrained machine can only store $m^{\prime}$ elements at a
time, and it is able to accurately count collisions on a comparison graph
$G=(V,E)$. Then it must be the case that

$\left|E\right|\leq m^{\prime}\cdot\left|V\right|$

######  Proof 5.10.

w.l.o.g let us name the vertices, or samples, by their order in the stream
$V=\left\\{v_{1},v_{2},\dots,v_{s}\right\\}$, and w.l.o.g let us think of the
edges in $E$ as ordered pairs (We only write $(i.j)\in E$ for pairs where
$i<j$).

Now, we note that at time $t$, upon processing the sample $v_{t}$, the memory
can only store $m^{\prime}$ samples from the set $s(v_{1}),\dots,S(v_{t-1})$.
This means that the number of edges in $E$ of the form $(v_{i},v_{t})$ is at
most $m^{\prime}$. Now, we can count our (ordered) edges using the second
item:

$\left|E\right|=\sum_{v_{j}\in V}\left|\left\\{(u,v_{j})\in
E\medspace|\medspace u\in V\right\\}\right|\leq\sum_{v_{t}\in
V}m^{\prime}=\left|V\right|\cdot m^{\prime}$

which completes the proof.

##### Centralized model with memory constraints.

We next apply this claim to give similar lower bounds in the following models.

######  Corollary 5.11.

Assume Conjecture 5.5 holds. In order to test uniformity in a memory-
constrained machine, using a collision-based tester and storage of up to
$m^{\prime}=\Theta\left(m/\log(n)\right)$ samples at any given time, one must
have

$q\geq\Omega\left(\frac{n\log(n)}{m\epsilon^{4}}\right),$

where $q$ is the total amount of samples used by the algorithm.

######  Proof 5.12.

As our measure complexity is the total amount of samples, $q=\left|V\right|$,
we can combine the claim above with Conjecture 5.5 to get:

$q=\left|V\right|\geq\frac{\left|E\right|}{m^{\prime}}=\Omega\left(\frac{n\log(n)}{m\epsilon^{4}}\right),$

which ends the proof.

##### Simultaneous model with memory constraints.

We observe the combined model of simultaneous model with memory-constrained
machines. We again restrict ourselves to a specific framework: each player
uses her own graph $G_{i}=(V_{i},E_{i})$, where memory is allocated for
sampled elements, and then all players send a short message to the referee.
The entire comparison graph the algorithm is based on is
$G=\bigsqcup_{i}G_{i}$.

######  Corollary 5.13.

Any collision-based uniformity tester in a simultaneous model of $k$ machines
that can store up to $m^{\prime}$ samples each, must use

$q^{\prime}=\Omega\left(\frac{n}{k\epsilon^{4}}\cdot\max\left\\{\frac{\log(n)}{m},\frac{\sqrt{k}\epsilon^{2}}{\sqrt{n}}\right\\}\right)$

samples per player, assuming Conjecture 5.5 holds .

######  Proof 5.14.

We start be re-writing the desired expression:

$q^{\prime}=\Omega\left(\max\left\\{\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}},\frac{n\log(n)}{mk\epsilon^{4}}\right\\}\right)$

We show the two lower bounds separately, resulting in a lower bound of the
maximum term.

Indeed, the first lower bound can be derived directly from Corollary 5.6:

$q^{\prime}=\Omega\left(\sqrt{n/(k\epsilon^{2})}\right)$

For the second lower bound, we extend Corollary 5.11 instead. As each $G_{i}$
is done by a machine with memory constraints, we apply Claim 1 to player $i$
and get $\left|V_{i}\right|\geq\left|E_{i}\right|/m^{\prime}$. We recall that
our measure complexity is in fact $q^{\prime}:=\max_{i}\left|V_{i}\right|$,
and as the maximum is greater than the average, we get:

$q^{\prime}\geq\frac{\sum_{i}\left|V_{i}\right|}{k}\geq\frac{\sum_{i}\left|E_{i}\right|}{m^{\prime}\cdot
k}=\frac{\left|E\right|}{m^{\prime}\cdot k}$

And plugging in Conjecture 5.5 on the entire graph $G=(V,E)$, we get

$q^{\prime}=\Omega\left(\frac{n}{m^{\prime}\cdot
k\epsilon^{4}}\right)=\Omega\left(\frac{n\log(n)}{m\cdot
k\epsilon^{4}}\right),$

concluding the proof.

###  5.3 Discussion

We point out to the fact that in all $4$ models (as well as the classic
model), the limitation of this method coincide with the upper bounds we
obtained in the previous section. This does not come as a surprise, since the
choice of the “right” comparison graph is easily made once the constraints
each model imposes are understood. The guiding rule is rather straightforward:
compare all pairs that can be compared.

It is more interesting, though, to see how well the collision-based testers
perform compared to known impossibility results (ones which apply for any
uniformity tester, and not only collision-based). It turns out for the most
part, these testers compete well with others.

For the classical model, as already established in [14], collision-based
testing is in fact optimal in all parameters.

For the two simultaneous models (with no memory constraints), the collision-
based testers perform optimally in terms of $n,k$ (or $n,(R_{1},\dots,R_{k})$
in the assymetric case). To the best of our knowledge, the only testers for
these models that consider multiple samples per processor are the ones of
[17]. The same asymptotic sample complexity is obtained in both papers (for
both models), but there are two non-trivial differences. On the downside, the
new testers use $\log\left(\Theta(1/\epsilon^{4})\right)$ bits per
communication, instead of a single one used in [17]. On the upside, the new
testers work for the full range of the parameter $k$ (the number of players),
whereas the previous results excluded extreme values: e.g., in the symmetric
case it only works for $c/\epsilon^{4}\leq k\leq c^{\prime}n\epsilon^{4}$.

Lower bounds for these two models are shown in [23], both for a single bit,
and the general case of $\ell$-bit messages. While the tester of [17] is an
optimal one-bit protocol, ours is not known to be optimal $\ell$-bit protocol.
This is true as the aforementioned lower bound weakens by a factor $2^{\ell}$
for the longer $\ell$-bit messages. In our case, we have
$2^{\ell}=\Theta(1/\epsilon^{4})$, which means there is a gap of
$\epsilon^{4}$ between the general lower bound, and the optimal collision-
based tester we obtain.131313Despite the gap, no better tester is known for
this amount of bits and $q>1$ samples per player. It still might be the case
that collision-based testers are optimal in this regime

In the streaming model our tester attain the same sample complexity as the
best known tester (that of [13]), but for a wider range for the parameter $m$.
A matching lower bound can also be found in [13], but only for a more
restricted range of the parameter $m$, whereas for the general case they give
a weaker lower bound, which leaves an $\epsilon^{2}$ gap between the general
case and the optimal collision-based tester.

To the best of our knowledge, the simultaneous model with memory constraints
was never considered in the context of distribution testing, and therefore
there are no prior results. However, we conjure that similarly to before, the
collision-based tester achieves optimal sample complexity in parameters
$n,k,m$, with a possible $\operatorname{poly}(\epsilon)$ gap that would pop,
as before, due to the use of longer messages.

## References

  * [1] Jayadev Acharya, Sourbh Bhadane, Piotr Indyk, and Ziteng Sun.  Estimating entropy of distributions in constant space.  In Advances in Neural Information Processing Systems, pages 5162–5173, 2019.
  * [2] Jayadev Acharya, Clément Canonne, Cody Freitag, and Himanshu Tyagi.  Test without trust: Optimal locally private distribution testing.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2067–2076, 2019.
  * [3] Jayadev Acharya, Clément L Canonne, Yanjun Han, Ziteng Sun, and Himanshu Tyagi.  Domain compression and its application to randomness-optimal distributed goodness-of-fit.  In Conference on Learning Theory, pages 3–40, 2020.
  * [4] Jayadev Acharya, Clément L Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi.  Interactive inference under information constraints.  arXiv preprint arXiv:2007.10976, 2020.
  * [5] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Distributed signal detection under communication constraints.  In Conference on Learning Theory, pages 41–63. PMLR, 2020.
  * [6] Jayadev Acharya, Clément L Canonney, and Himanshu Tyagiz.  Inference under information constraints i: Lower bounds from chi-square contraction.  IEEE Transactions on Information Theory, 2020.
  * [7] Jayadev Acharya, Clément L Canonney, and Himanshu Tyagiz.  Inference under information constraints ii: Communication constraints and shared randomness.  IEEE Transactions on Information Theory, 2020.
  * [8] Kareem Amin, Matthew Joseph, and Jieming Mao.  Pan-private uniformity testing.  In Conference on Learning Theory, pages 183–218. PMLR, 2020.
  * [9] Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki.  Two party distribution testing: Communication and security.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019\.
  * [10] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White.  Testing that distributions are close.  In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 259–269, 2000.
  * [11] Manuel Blum, Michael Luby, and Ronitt Rubinfeld.  Self-testing/correcting with applications to numerical problems.  Journal of computer and system sciences, 47(3):549–595, 1993.
  * [12] Clément L. Canonne.  A survey on distribution testing: Your data is big. but is it blue?  Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015.
  * [13] Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, and Sankeerth Rao.  Communication and memory efficient testing of discrete distributions.  arXiv preprint arXiv:1906.04709, 2019.
  * [14] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Sample-optimal identity testing with high probability.  CoRR, abs/1708.02728, 2017.
  * [15] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Collision-based testers are optimal for uniformity and closeness.  Chicago Journal OF Theoretical Computer Science, 1:1–21, 2019.
  * [16] Ilias Diakonikolas and Daniel M. Kane.  A new approach for testing properties of discrete distributions.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 685–694, 2016.
  * [17] Orr Fischer, Uri Meir, and Rotem Oshman.  Distributed uniformity testing.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, New York, NY, USA, 2018. ACM.
  * [18] Sumegha Garg, Pravesh K. Kothari, and Ran Raz.  Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), pages 21:1–21:18, 2020.
  * [19] Oded Goldreich.  Introduction to Property Testing.  Cambridge University Press, 2017.
  * [20] Oded Goldreich.  The uniform distribution is complete with respect to testing identity to a fixed distribution.  In Computational Complexity and Property Testing, pages 152–172. Springer, 2020.
  * [21] Oded Goldreich, Shari Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM (JACM), 45(4):653–750, 1998.
  * [22] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  Electronic Colloquium on Computational Complexity (ECCC), 7(20), 2000.
  * [23] Uri Meir, Dor Minzer, and Rotem Oshman.  Can distributed uniformity testing be local?  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 228–237. ACM, 2019.
  * [24] Varun Narayanan, Manoj Mishra, and Vinod M Prabhakaran.  Private two-terminal hypothesis testing.  arXiv preprint arXiv:2005.05961, 2020.
  * [25] L. Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 54(10):4750–4755, 2008\.
  * [26] Ronitt Rubinfeld and Madhu Sudan.  Robust characterizations of polynomials with applications to program testing.  SIAM Journal on Computing, 25(2):252–271, 1996.
  * [27] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing, 46(1):429–455, 2017.

##  Appendix A Is every edge a blessing?

In our results the guiding rule in any model was “compare every pair the model
allows you to”. However, this intuitive rule was not formalized, and it could
be for a good reason. Earlier, in Section 5.3, we posed the question of
whether adding another edge (another comparison) to the entire average, can
hurt our assessment of the collision probability, and thus weaken our tester.

We leave it as an open question whether the actual reliability of the tester
can only get better when adding edges (or rather, under which circumstances it
is true). For now, we do point out a pathological yet surprising example where
a comparison graph $H$ that fills the requirements of Theorem 3.1 for some
constant threshold $\tau$, is a subgraph of $G$ that is not good for any
constant threshold $\tau^{\prime}$.

Obviously, the number of edges only goes up when adding edges, so for such an
example we should focus on breaking the third condition in Theorem 3.1, by
making the supergraph $G$ one with a large amount of $2$-path. Indeed, this is
possible: Consider $H$ to be the simple cycle of size
$b\cdot\frac{n}{\epsilon^{4}}$, for some constant $b$. It holds that
$c(H)=2\left|E_{H}\right|=2\left|V_{H}\right|=2b\cdot\frac{n}{\epsilon^{4}}$.
Taking large enough $b$ (as a function of $\tau$) would give us $H$ that fills
the three conditions of the theorem, as
$c(H)/\left|E_{H}\right|^{2}=1/(2\left|E_{H}\right|)=\frac{\epsilon^{4}}{2n}$.
So indeed $(H,\tau)$ is a good tester.

The supergraph $G$ of $H$ would be this: we choose one the vertex $v$ in $H$,
and connect it with all other edges. Now $G$’s edges are either part of a star
or a cycle. $\left|E_{G}\right|=2\left|V_{G}\right|-3\leq
2\left|V_{G}\right|$, but the star gives us $c(G)\geq\left|V_{G}\right|^{2}/3$
(Solely by the 2-paths with $v$ as the middle vertex). This means that

$\frac{c(G)}{\left|E_{G}\right|^{2}}\geq\frac{\left|V_{G}\right|^{2}/3}{(2\left|V_{G}\right|)^{2}}=\frac{1}{12}$

So for _any_ constant threshold $\tau^{\prime}$ and asymptotic values of
$n,\epsilon$, Theorem 3.1 cannot be applied for $(G,\tau^{\prime})$.