Replicable Distribution Testing
Authors: Ilias Diakonikolas
Jingyi Gao
Daniel Kane
Sihan Liu
Christopher Ye
Venue: NeurIPS 2025 spotlight ()
Keywords: Replicability
Distribution Testing
Primary area: theory
TL;DR: We study replicable distribution testing.

Abstract: We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, we develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity testing---answering an open question from prior work---and closeness testing.

Replicable Distribution Testing
Ilias Diakonikolas University of Wisconsin-
Jingyi Gao
University of Madison jingyig@cs. wisc.
ilias@ca. wisc. edu
Daniel M. Kane
Sihan Liu University of California, San Diego La Jolla, CA si1046@ucsd.
University of California, San Diego dakane@cs. ucsd. edu
Christopher Ye
University of California, San Diego La Jolla, CA czye@ucsd. edu
Abstract
We initiate a systematic investigation of distribution testing in the framework algorithmic replicability. Specifically, given independent samples from collection probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity an open question from prior work-and closeness testing.
Introduction
Algorithmic replicability has emerged as fundamental notion in modern statisties and machine learning to ensure consistency of algorithm outputs in the presence of randomness in input datasets. The formal notion of replicability, proposed in Impagliazzo et al. [2022], is as follows.
Definition 1.1 (Replicability Impagliazzo et al. [2022]). A randomized algorithm A: X + is p-replicable if for all distributions on X, PI..T. (A(T;r) = r(T";r)) Z 1- - p, where T, T are i..dd. samples taken from p. and denotes the internal randomness of the algorithm A.
Since its introduction, replicability has been considered in the context of a wide range of machine learning tasks, including multi-arm bandits Esfandiari et al. [2022], clustering Esfandiari et al. [2023], reinforcement learning Karbasi et al. [2023], Eaton et al. [2023], halfspace learning Kalavasis et al. [2024], and high- dimension statistics Hopkins et al. [2024]. A related line of work explored the connection between replicability and other algorithmic stability notions such as differential privacy Bun et al. [2023a], Moran et al. [2023], total variation indistingushaabiiity Kalavasis et al. [2023], global stability Chase et al. [2023], and one-way perfect generalization Bun et al. [2023a], Moran al. [2023].
In this work, we initiate systematic study of replicability in distribution testing, a central area in property testing and statistics that aims to ascertain whether unknown distribution satisfies certain property or is "far" from satisfying that property. Specifically, we focus on replicable testing of discrete distributions in total variation distance, which encompasses canonical problems such as uniformity/ddentity testing, closeness testing, and independence testing. Formally, we have:
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Definition 1.2 ((c, reeeplibll testing of property P). Let P be property consisting of k- tuples of distributions, and p. E (0, 1/4). Given sample access to a collection of distribu- tions pil..... -p(k, we say randomized algorithm A solves (c, (e.p)-rellicable P-testing if A is g-replicable and can distinguish between the following cases with probability at least 1 p. completeness case (p!)), ,... ......'' ..)...)))))))) E P or soundness case k- Σ'= drv (p (()) 2 for all ruples
-(t)) ) E P. particular, (a) uniformity testing over the domain [n]] corresponds to the case that k = 1, and P consists of only the uniform distribution over [n]: (b) closeness testing over the domain [n]] corresponds to the case that k 2, and consists of all pairs of distributions (p. p) over [n]; (c) independence testing over domain [re] x [m2] corresponds to the case that k = 1, and P consists of all product distributions over that domain.
After the pioneering works formulating this field Batu et al. [2000], Goldreich and Ron [2011] from a TCS perspective, a line of work has given efficient testers (without the replicability requirement) achieving information theoretically optimal sample complexities for the aforementioned problems; see Paninski [2008], Valiant and Valiant [2017] for uniformity/identiy testing, Batu et al. [2000], Valiant [2008], Batu et al. [2013], Chan et al. [2014] for closeness testing, and Batu et al. [2001], Acharya et al. [2015], Diakonikolas and Kane [2016] for independence testing. More broadly, substantial progress has been made on testing wide range of natural properties; see, e.g., Batu et al.
[2002, 2004], Acharya et al. [2011], Levi et al. [201 1], Diakonikolas et al. [2015], Canonne et al.
[2017], Daskalakis et al. [2018], Canonne et al. [2018. 2022b,a] for sample of works, and Rubinfeld [2012], Canonne [2020, 2022] for surveys on the topic.
Despite the maturity of the field of distribution testing. the relevant literature contains only a single prior work addressing replicability: a recent paper by Liu and Ye [2024] designs replicable testers for the task of uniformity testing (and identity testing via standard reduction technique), and demonstrates that the sample complexity is nearly tight within a restricted class of algorithms. Specifically, their techniques are insufficient to establish lower bounds against general uniformity testers, or to design sample-optima replicable testers for other distribution testing problems.
An instructive parallel arises in the context of differentially private (DP) distribution testing, where similar challenges in designing testers with extra stability constraints have been addressed:see Cai et al. [2017], Aliakbarpour et al. [2018], Acharya et al. [2018], Aliakbarpour et al. [2019]. Although generic reductions from DP to replicable algorithms exist, see, e.g., Bun et al. [2023b], they incur polynomial overheads in sample complexity. This motivates our goal: to develop a principled and fine-grained understanding of the sample complexity cost of replicability in distribution testing.
1.1 Our results
Our first main contribution is a new lower bound framework for replicable distribution testing that yields unconditional lower bounds against all testers, without additional assumptions. As first application of our framework, we show that the replicable uniformity tester proposed in Liu and Ye [2024] is indeed nearly optimal, thus settling the main open problem left by their work.
Theorem 1.3 (Sample Complexity of Replicable Uniformity Testing). The sample complexity of (c, reepplibbbblee uniformity testing over [n] is O(yTee-2p" =
+
We believe that the framework is broadly applicable to establishing lower bounds for other replicable distribution testing problems. In partieular, as additional application, we derive the following tight lower bound for replicable closeness testing.
Theorem 1.4 (Lower Bound of Replicable Closeness Testing). The sample complexity of (E, p)- replicable closeness testing over [n] is at least Q(n2/3 p/ 2/3 + vne + + 2
On the algorithmic front, provide new replicable testers for closeness and independence testing. For closeneness testing, we show:
Theorem 1.5 (Replicable Closeness Tester). The sample complexity of (e, rerelliccbble closeness testing over [n] is at most g -2/3
2/3 + Vne-2 p-1 + 222-)
Note that Theorem 1.5, together with Theorem 1.4, give a tight characterization of the sample complexity of replicable closeness testing up to polylogarithmic factors. For independence testing, show that:
2

---

Theorem 1.6 (Replicable Independence Tester), The sample complexity of (E: re-eplialla indepen- dence testing over [n1] x [n2] for n1 2 n2 is at most Ô 2//3n// vning
Pe
Perhaps surprisingly, our upper bounds point to an intriguing conceptual connection between repli- cability and distribution testing in the high success probability regime. In particular, the functional forms of the sample complexities of (non noo-reppic)ble) uniformity, closeness, and independence testing up to error probability ó have been characterized in Diakonikolas et al. [2018, 2021] to be preciscly the sample complexity upper bounds of the corresponding replicable testing problems after replacing p- with y (log(1/5)² 2. Moreover, all known replicable distribution testers (including ours) leverage the statistics developed in the context of high probability distribution testers. We leave as an interesting open problem whether there exists generic reduction from high-probability testers to replicable ones vice versa. Lastly, with this connection in mind, it is a plausible conjecture that our sample complexity upper bound for replicable independence testing is nearly optimal. We leave this as an open question.
1.2 Technical Overview
We start with a description of our lower bound framework, which is the main technical contribution of this work, followed by our upper bounds.
Replicable Testing Lower Bounds In what follows, we will sketch the overall framework for showing lower bounds against replicable uniformity and closeness testing, and point to the specific lemmas used in deriving the uniformity testing lower bound for concreteness. Let A be a randomized tester for the testing problem that uses significantly fewer samples than the target lower bound. Our end goal is to show that if A satisfies the correctness requirements of the corresponding testing problem, then A cannot be replicable. Towards this goal, we begin with the same reasoning steps as the ones in Liu and Ye [2024]. In particular, we construct a meta- mnta-distribution Mę. parametrized by E E e). over potential hard instances of the testing problem such that (i) MM and Mr correspond to instances that should be respectively accepted and rejected by the tester, and (ii) it should be hard to distinguish random instance from MM versus a random instance from Mgtep-
After that, using the same argument as Liu and Ye [2024], we can deduce that if we sam- ple & el), then the average acceptance probability of the tester under MM. i.e., Ep-M, [Prs=p [A accepts SI]. will be close to 1/2 with probability at least l(p) over the random- ness of f. See Lemma 3.5 for the formal statement. If MM were to contain just single distribution instance Pş. then the statement would directly imply that A is not replicable under Pş. and this would conclude the lower bound argument. Of course, Me is in reality meta- deta-distribution over (exponentially) many different instances by design (see Definition 3.2). To overcome this issue, Liu and Ye [2024] takes advantage of the fact that the instances from the mett-distribution are identical up to permutation of the domain elements. As such, if one makes the additional assumption that the output of the tester is invariant up to domain relabeling (in other words, the tester symmetric), then it is not hard to show that the acceptance probability of the tester under each individual distribution must be the same as the overall averaged acceptance probability under Mg, and the proof is complete.
Our proof circumvents this difficulty with a fundamentally different approach that allows us to avoid making any assumptions on the tester. As one of our main technical contributions, we show that even when the tester is not symmetric, the acceptance probability under random choice of p ~ MM must nonetheless concentrate around its expectation, as long as the tester is still moderately replicable under p. i.e., replicable with probability 1 1/polylog(n) See Lemma 3.6 for the formal statement. Towards this goal, consider the joint distribution of two random sample sets S, generated as follows: pick a random distribution p ~ Me and then sample S, S" independently from p pmm The distribution of S" conditioned on then naturally defines a random walk RWg on the space of all possible sample sets. For convenience, denote by RW obtained by first sampling T p and then performing & steps of the random walk. Lying in the heart
E (p) the distribution over sample sets 5
'While our replicable closeness tester runs in linear time in sample size, our replicable independence tester requires polynomial runtime. This is due to an extra "averaging" operation applied to make the statistic more stable (see Section 1.2). We leave it for future work to explore whether its runtime can be further improved. FFor example, the sample complexity high probability closeness testing has been shown to be @ (n2/3=-4/1 (1200/ + vin- Vog(1188 + (lg((16))) by Diakonikolas et al. [2021]
3

---

of our proof is the following two structural claims: (I) for most p ~ Mgg. the acceptance probability of the tester under R (owlooylog()) (p) is roughly the same as that of under p. (2) the random walk
RW; has mixing time at most polylog(n). Combining the two claims gives that the acceptance probability under most p ~ Me must be roughly the same, as the acceptance probability under the stationary distribution of the random walk (which by construction is exactly equal to the expected acceptance probability under .Mg).
then remains for us to establish these two claims. The proof of (1) mainly follows from the definition of the random walk, and the assumption that the tester is moderately replicable. See Lemma 3.9 and its proof for details. The canonical way for showing (2) is to bound from below the eigenvalue gaps of the transition matrix of the random walk. To analyze this, we note that after careful use of Poissonization (see Definition D.I for the definition of Poisson sampling), we can make RWe product of independent random walks. Formally, since the number of samples is Poissonized, the sample frequency of each bucket is independent, even conditioned on the choice of distribution p ~ MM-- It then suffices for to bound the mixing time of much simpler random walks on the sample frequencies of each individual domain element. Fortunately, the eigenvalue gap of this random walk can be analyzed conveniently using elementary properties of the Poisson distributions. See Lemma 3.8 and its proof for details. The formal proofs of Theorem 1.3 and the relevant lemmas are deferred to Appendix E.
Lastly, the same framework also applies to the proof of Theorem 1.5. The main change needed is to replace the meta-distributiin Me to be the standard hard instance for closeness testing, See, e.g., Valiant [2008]. Chan et al. [2014], Diakonikolas and Kane [2016] for the construction of the hard instance. The formal proof can be found in Appendix F.
Replicable Testing Upper Bounds We begin with the observation that many testers from the literature share the following nice form: compute a test statistic Z and compare it to threshold R. Usually, the analysis (without replicability requirements) involves showing that E [2] = 0 in the completeness case, E [2] >> R in the soundness case, and Var[Z] is at most a small constant multiple of R2, For testers of this form, we can employ the same strategy as the one used Liu and Ye [2024] transform them into replicable testers:
compute the same test statistic Z, and then compare it to a randomly chosen threshold r between 0 and R/2. In particular, if we further have that Var [Z] < R², p² (at the cost of taking more samples), the variance bound on Z implies that Z computed with different sample sets drawn from the same underlying distribution are likely to be close to each other. Consequently, the values of Z in two runs are unlikely to be separated by randomly chosen r, ensuring replicability.
For closeness testing, the high probability tester from Diakonikolas et al. [2021] satisfies exactly the conditions needed, and in turn yields our replicable tester after combining it with the random thresholding strategy. The formal proof of Theorem 1.5 is given in Appendix C.
Designing good testers for replicable independence testing turns out to be significantly more involved, as even the known high probability independence testers do not satisfy the required variance bounds within our sample complexity budget. In its essence, the bottleneck lies in an extra randomized "flattening" procedure employed by the tester, which significantly increases the overall variance of the final statistic computed. Specifically, the procedure utilizes a random subset of the input samples to "split" domain elements with large mass into sub-elements. This step aims to ensure that there will be no extremely heavy elements after the procedure (otherwise, the tester may fail to satisfy even the basic correctness requirements). To show correctness of their tester, Diakonikolas et al. [2021] demonstrated that (1) the flattening procedure preserves the product/non-produs structure of the original distribution, and (2) the variance of the final test statistic conditioned on the flattening samples (and some other technical conditions) is small. Notably, a bound on the total variance of the test statistic Z is not needed in their context, as the above two properties suffice for them to show upper/lower bounds on 2 in the completeness/sonnness cases. Yet, when replicability is of concern, we do need to show that Z concentrates around small interval. As a result, the lack of a good bound on the total variance (as compared to just conditional variance) of the final test statistic turns out to be a major technical obstacle in converting the high probability tester into a replicable one. In fact, the randomness in using different samples for flattening purposes can easily cause the total variance of Z to be much larger than the conditional variance.

---

To overcome this difficulty, we leverage the following idea from Aliakbarpour et al. [2019] (in the context of differentially private testing): to make a test statistic computed with internal randomness more stable, we can replace it with the averaged version of it. In particular, we apply this idea to the statistic Z computed by the high probability independence statistic, and obtain a new averaged statistic Za ea-sssentillyy the expected value of Z averaged over all possible partitions of the input samples into flattening samples and testing samples (see Definition 2.6 for the formal definition). As our main technical lemma, we show that the total variance of this averaged test statistic Za can be bounded from above by N-the expected value of the number of non-singleton samples, i.e., the testing samples which still collide with another testing sample after the flattening procedure (see Lemma 2.9). At a high level. our argument uses an Efron-Steen style inequality that bounds the variance by the sum of the expected square differences of the test statistic Zo caused by removal of each individual sample. Suppose that there are in total m samples and the probability of selecting sample for flattening is p. We then proceed by case analysis. If the sample removed is used for computing the final test statistic, we show that the (non-averaged) test statistic Z will only be different if the sample also happens be singleton sample after flattening, which happens with probability roughly (NN /m). If the sample is selected for flattening, we show that removing it can change the test statistic 2 by at most N divided by the number of flattening samples, which is roughly O(pm). Consequently, the contribution to the variance of Zu in this case is at most (p N/(mp))) S N² 1P/mm. which is also O(N/m).
It remains for us to control the non-singleton sample count N. Fortunately, Diakonikolas et al. [2021] already established sharp bounds on the expected value of N, when p is known to be a product distribution. This then motivates us to run pre-test to check whether E[N] is within a constant factor of the desired bound, before computing the averaged independence statistic Za. In particular, we consider the statistic Na. defined similarly to Zu as the expected non-singleton sample count N averaged over the random choice of the flattening sample set, and use an almost identical argument to show that Var [Na[N can also be bounded by O [N]) (see Lemma 211 Equipped with the variance bound, it is not hard to show that comparing Na with an appropriately chosen random threshold yields tester that replicably determines whether the magnitude of E N] is within a constant factor of the bound it should satisfy when p is a product distribution. If we pass this test, we can then proceed to apply the main test, which compares Za to a randomized threshold. This concludes our proof sketch. The relevant lemma statements can be found in Section 2. The proofs of Theorem 1.6 and the relevant lemmas are deferred to Appendix B.
Preliminaries Let [n] = (l...., n). We use n to denote domain size and m to denote sample complexity. We use bold letters (e.g. P. q) to denote distributions or measures and p(1) to denote the mass of under p. Let Poi(A) denote a Poisson distribution with parameter X and PoiS(m, p) denote m' Poi(m) i.i.d. samples from p. Let Bernoulli (a) denote a Bernoulli distribution with parameter a. Let (SS) denote the uniform distribution over set S, where S can be either a discrete set of points or an interval. For any distribution p. let p pmm denote m i..d, samples from p. We use "algorithm" and "tester" interchangeably. For multiset S of samples, we denote the set of all elements appearing in S by sSp.
2 Replicable Independence Testing Algorithm
In this section, we give our replicable independence tester. At high level, we compute the same statistic used by the high probability independence tester from Diakonikolas et al. [2021], but average over the internal randomness of the tester to enhance replicability.
Our starting point is the (randomized) flattening technique developed in Diakonikolas and Kane [2016], Diakonikolas et al. [2021] that helps decrease the &g norm of input distributions while maintaining the properties to be tested in total variation distance. The original description as follows. First, one draws a set of samples X, and randomly partitions X into a flattening sample set, and testing sample set. Next, one uses the flattening samples to determine the number of sub-bins for each original domain element, and then randomly assigns original testing samples to the sub-bins. For our analysis, it is more convenient to consider an equivalent random process, where we randomly sort all samples, partition them into flattening and testing samples, and make two testing samples be in the same sub-bin if and only if they are originally from the same bin and there are no flattening samples from the same bin between them. The formal description is as follows.
5

---

Definition 2.1. Let [x,, be multiset of samples over [n], and F E 10,1) th be a bi- nary vector. Then the randomized flattening procedure X == {X² Je,F,=0 t- Flatten( (Xe) ) )= F) is as follows. (1) Assign a random order a to the samples. (2) For each sample Xt. count the number of samples Xe before it according
such that Xe X and Fe = 1. Denote the number as Se- (3) For each l such that Fe O, X (Xx; Moreover, given parameter a E (0, 1), we denote by Flatten(X;;0 the randomized sample set obtained from X + Flatten(X;; F), where F ~ Bernoulli(a)ss 8m
In independence testing, we need to perform the flattening operation on the marginals of multi- dimensional distribution independently. For clarity, we formalize this operation below.
Definition 2.2. Let a, 3 E (0, 1), and P = {Pr = (Xe, )o) be a multiset of samples over [mi] x [12).. Then the multi-dimension flattening operation Pl == {P/} < Flatten(
as follows. (I) Choose F Bernoulli(a))) pmom and F Bernoull((3omm (2) {X, besf== & Flatten( [Xe) 1i FT), (Y/ be,7 + Flatten (Xe)ee F.). (3) Map Pe to P + (X YE! if FT = F2 = O. When flattening two bags of samples A and B together, we denote by A U Bf + Flatten A U B; ax B), where A (B', resp.) contains all elements mapped A(B, resp.).
Another key idea behind the tester from Diakonikolas et al. [2021] is to use the samples from p to simulate samples from another product distribution q that equals to the product of the marginals of P. In particular, sample from q can be simulated by taking two samples from p, and combining the first coordinate of the first sample to the second coordinate of the second sample. Hence, we can readily assume that we have sample access both p and q.
Definition 2.3 (Product of Marginals). Given a distribution P over [Ma]] x [12),, we say q is the product of marginals of p if the marginals of q agree with that of p and q is a product distribution.
Given the samples from the original distribution, and the ones from the product of the marginals, the final step of the tester from Diakonikolas et al. [2021] is to compute the closeness test statistic, which we reiterate below.
Definition 2.4 (Closeness Statistic), Given two bags of samples Sp: Sq over some finite discrete domain, the closeness statistic (c(Sp. p. Sq) is defined as follows. (1) For each sample in S.S. mark it independently with probability 1/2. (2) For i E supp (Sp U U.S.). let T T be the number of times the element appears marked Sp. S., and T T be the corresponding counts of the unmarked
samples. (3) Compute Zc(Sp. + [T"" T:00 + IT - T (T.0 TTP TTT T7
useful fact of this test statistic is that any singleton sample does not contribute to its value.
Fact 1. Consider two sets of samples Sp. Sq over some finite discrete domain. Assume that P singleton sample among Sp U S.. It holds that (Sp Sy]] = EE ( (P)) S,MPH, where the randomness is over the internal randomness of the test statistic Z.
We are now ready to state the tester from Diakonikolas et al. [2021], which forms the building block of our replicable independence tester.
Algorithm 1 INDEPENDENCESTATS
Input: sample set Sp from the unknown distribution p over [n1] x [nz]. where n1 2 n22, and another sample set S, from q. the product of marginals of p.
Parameters: domain sizes n1 > n2 tolerance e E (0, 1/4). replicability & E (0. 1/4).
Output: A test statistic related to whether these samples came from an independent distribution.
1: Set m = è / n22 p 2//3-1/3 4/3 + Vningg--ee- + p 2-2=-2
2/3 1/3
2: Set a = min(n1/// (100m). 1/100), B n2/ (100m)
3: Compute the flattened samples S U S <- Flatten (Sp U Sy: a, 13).
4: Abort and return 0 if |Spl - | > 10n; or |s,1 - | > 10nz.
5: Sample f, L' ~ Poi(m). Abort and return 0 o > |5 or l > |
6: Keep only the first l samples of s and only the first l' samples of s!.
4.
7: Compute and return the closeness test statistic Zc(S S().

---

A basic property we need is that the final test statistic computed has a wide expectation gap.
Lemma 2.5 (Expectation Gap of Independence Statisties; Section 3.2 and Claim 4. 14 of Diakonikolas
et al. [2021], Let p be some unknown distribution over [nr] x [mz], q be the product of marginals of and m be defined as in Line 1 of INDEPENDENCESTATTS Let Sp. Sy be samples from p. q respectively with size |Spl = [ = 100m, and Z + INDEPENDENCESTATS (Sp. S Define G := min (Em,m²²² m²²² (m112)), m²/²2²/ (minz) I is product distribution, then Eiz] < Cr, G;
If p is E-far from any product distribution in TV distance, then E|Z] > G for some constants Cr < Cc2-
To make the final test statistic computed by INDEPENDENCESTATS more replicable, we consider a new test statistic Ze computed by averaging over the internal randomness of INDEPENDENCESTATS.
Definition 2.6 (Averaged Independence Statistic). Let Sp: Sy be samples over [m1] [m2] We define Za S₂) to be the expected value of INDEPENDENCESTTAT (S,, S,)) averaged over the internal randomness of INDEPENDENCESTATT.
An important quantity in analyzing the concentration of the above new statistic is the concept of non-singleton sample counts.
Definition 2.7 NNon-singleton Sample Count). Let S be a set of samples over some finite discrete domain. We define the non- singletnn sample count N (S) the total number of samples within S that collide with another sample.
Specifically, we focus on the non-singleton sample count of the flattened sample sets St. St con- structed by INDEPENDENCESTATS.
Definition 2.8 (Non-singleton Sample Count of Flattened Samples), Let Sp. Sq be two arbitrary sets of samples over [m1] x [ma]. Consider the two random (truncated) flattened sample sets S St con-
structed by INDEPENDENCESTAAS,, where the expectation is over the internal randomness of INDEPENDENCESTNTS.
on Line 7 3. We define (a Sy) == E (N(S/ U S()).
Our main insight is that we can bound the variance of the new statistic Z. (Sp, S.)) by the expected value of No (Sp. Sq). This key technical lemma is as follows. The proof deferred to Appendix B.
Lemma 2.9 (Bound Variance of Averaged Independence Statistic in Expected Non- Von-Singleton Sample
Count). Let p be a distribution over [n1] [122], and q be the product of marginals of p. Ler Sp. Sg be samples from p. respectively. Consider the averaged independence statistics Za (a(Sp. Sq). and the averaged non-sing non-singleton sample count N (Sp Sq)- Then holds that Var ZZa (Sp. Sq)1 S Oloo""( (S,
where the randomness is over the samples Sq.
It then remains for us to control Na (Sp. Sg). Fortunately, the expected value of the non-singleton count has already been shown to be small by Diakonikolas et al. [2021] when the underlying distribution p is known to be a product distribution.
Lemma 2.10 (Expected son-singleton Sample Count under Product Distribution, Lemma 4.9 of Diakonikolas et al. [2021]). Let m E Z4, a. E 1) be defined as in Line I and Line 2 from INDEPENDENCESTATE respectively. Let S be samples from a product distribution q over [n,] x [ng] with |S| = 100m. Consider the random variable NS$)), where St + Flatten(S a. B). Then there exists universal constant ON such that [[N(S5) S ON max (m²/ (m)n2), m/nz).. where the randomness is over the internal randomness of Flatten(.) well as the sumples.
This motivates a two-stage testing strategy: we can first test that the expected value of (s, U.S.). S,), is sufficiently small, and then compute the averaged statistic Z, (Sp.. S,). To ensure replicability of the first testing stage, we also need to control the variance of the averaged non-singleton sample count N₂ (S, U S.y. Fortunately, the variance can be bounded in the same way as the variance of the averaged independence statistic Za (Sp U Sq). See Appendix for the detailed argument.
Lemma 2.11 (Bound Variance of Averaged Non-Singleton Sample Count). Let P be a distribution over [n1] [ng], and q be the product of marginals p. Let Sp. S, be samples from p. q respec- tively. Consider the random variable Na (S, Sq) defined as in Definition& 2.8. Then it holds that
Var[N. (Sp, S.)] < Olog' (1122) (Sp, Sq)], where the randomness is over Sp, Sq.
We think of the two sets being empty if the algorithm aborts before reaching Line 7
7

---

Using Lemma 2.11, we show that we can replicably test whether (Sp, Sq)l is on the order of
max (m²)/111g)) m/ min(n1, m22)) by simply drawing random sample sets Sp. Sg. (approximately) computing (Sp. Sq), and then comparing it with an appropriately chosen random threshold.
We are now ready to present our full independence tester. The full analysis and proof of Theorem 1.6 can be found in Appendix B.
Algorithm 2 REPINDEPENDENCESTHIS
Input: sample access to an unknown distribution p over [n1] x [12]
Parameter: E (0, 1/4) tolerance, P E 1/4) replicability.
Output: Whether p is product distribution.
1: Let be defined as in Line 1 of INDEPENDENCESTATS.
2: Sp f 100m samples from p. and S., + 100m samples from q, the product of marginals of p.
3: Estimate Nu (.p5ssg) S.)) (see Definition 2.8) up
error o(1) by running
INDEPENDENCESTTATS
S.)) with fresh randomness for sufficiently many times.
4: Draw r ~ U([2CN, 10)C,]), where CN is the constant from Lemma 2.10.
5: Reject if (estimated) No (Sp. 5q)) > r max (m22(() ( m//2)..
6: Sp < 100m samples from p. and S.y f- 100m samples from q. the product of marginals of p.
7: Estimate (S, (see Definition 2.6) up to error o(1) by running INDEPENDENCESSTATS(SS with fresh randomness for sufficiently many times.
8: Draw r ~ U([CI, C1,)), where Ct Ct2 are constants from Lemma 2.5.
9: Reject if (estimated) Za(Sp. Sq) > r min (sm, m²s² (2ini))))))))))))))))))))))))))) m Vnin2). Otherwise, accept.
3 Lower Bounds for Replicable Uniformity Testing
In this section, we show the sample complexity lower bound ń 2c- + Tne T for p)- replicable uniformity testing over [n]. The ((c-2p-2) part follows from the lower bound in Lemma 7.2 of Impagliazzo et al. [2022] for the naive case when = 2, i.e. distinguishing fair from biased coin so we focus on establishing the lower bound (i(n 2--11 As such, we assume that ō (Vn==>p this section. To begin with, we apply common technique called Poissonization. Specifically, reduces the task into showing lower bounds against Poissonized testers allowing a more flexible sampling process from non- negative measures in place of the standard testers that are restricted to take fixed number of samples from distributions. Formally, the Poissonized tester is defined as follows.
E 2-2 which implies the implicit bound Vn=-20-1 = ō (n=-²), throughout
Definition 3.1 (Poissonized Tester and Poisson Sampling). Given non-negative measure over [n] and an integer m, the Poisson sampling model samples a number m! ~ Poi (milppli and draws m' samples from p/ ||pl|. Let T E R be the random vector where T3 counts the number of element i seen among the samples. We write PoiS(m, p) to denote the distribution of the random vector T. We say A is Poissonized tester with sample complexity if takes as imput T ~ PoiS(m, p).
Based on this, we can relax the hard instances for uniformity testing be in general non-negative measures over [n]. The definition below describes the meta- veta-distribution MM over non-negative measures over [n]] that forms the family of hard instances for uniformity testing.
Definition 3.2 (Uniformity Hard Instance). For E [0, we define MM to be the distribution over non-negative measures Pę defined follows: (i) ItS with probability 1 and 1- otherwise. " The hard instance Hy for replicable uniformity testing is given by first & u((0,=]), then P& ~ MM-
Using a standard minimax-style argument from Impagliazzo et al. [2022], it suffices to give a lower bound for deterministic algorithms (fixed random seed r) on random instance from Hy. More specifically, the task can be reduced to showing that any deterministic algorithm that satisfies distri- butional correctness w.r.t. Mo and M, cannot at the same time satisfy distributional replicability with respect to Hy-
Definition 3.3 (Distributional Correctnes/Reeliicbbltty... Let Mo, Mcs H be meta-distributions non-negative measures over [n]. Let A be a Poissonized tester with sample complexity m. (1)
8

---

We say A is S-correct w.r.f. Mo and MM Pr Mo, [A(T) Accept) 2 1 - 5 and Pr..p.... TT-PoS(mmp))) M.
[A(T) = Accept] S 6. (2) We say A is p-replicable with respect to H. if it holds that P.p=H.TTTTTPuattmm.. (A(T) F A(T")) S p.
We defer an elaboration on the reduction from showing lower bounds against deterministic Poissonized testers to those against randomized standard testers to Appendix D. Equipped with this reduction, the proof of Theorem 1.3 can then be reduced to the following main result of this section:
Proposition 3.4. Let Mg be the meta meta- distribbuttoonnnnno parametrized by [0, defined as in Defini- tion 3.2, A be deterministic Poissonized tester with sample complexity m ő (/m=-pp-) If A is 0.1-correct with respect to Mo and Me. then A cannot be plog n-replicable with respect to Ho-
From now on, we focus on the proof of Proposition 3.4. Since A is assumed to be deterministic tester, we note that of A(T) lies in the interval [1/3, 2/3]. For convenience, we define the function Accm((p.. A) := Prr-Pos(mm.) (A(T) = Accept) It then suffices for us to show
[A(T) & A(T")] 2 0.1 holds as long as the acceptance probability
Pr p~Hr
= n, 1 - log -2 2n)] 2 p. [Accm A) E (log -2
Recall that Hy is defined to first select randomly from [0. and then sample from the distribution family My. Hence, towards showing Equation (1), we will first show the intermediate result that the average acceptance probability Epp.MG [Acem (p. A)] is close to 1/2 with probability at least p over the random choice of Ç. At a high-level, we observe that the expected acceptance probability function must evaluate to exactly 1/2 for some & E (0,s) due to continuity, and then draws tools from information theory to show that the function is in general 0. (sp) (opp))--LLipshiie with respect to the parameter Ç. The argument is similar to the one employed in Liu and Ye [2024], and so we defer it to Appendix E. The formal statement is given below.
Lemma 3.5. Let A be deterministic Poissonized tester that is 0. -oorrccc w.r.t. Mo and Me and m- Ö(VTE ²p)1), then PTç-u((OoEE) [E [Acc, AD] E (1/3, 2/3) 2 p.
To conclude the proof of Equation (1), we then relate the acceptance probability Accm (p) for random ~ MM to its expected value. To achieve the goal, the authors from Liu and Ye [2024] exploit the assumption that the underlying tester symmetric. Our main technical contribution here is that we managed to remove this assumption. In particular, we show that even if the underlying tester not symmetric, the acceptance probability Acem (P) will nonetheless satisfy strong concentration properties as long as the tester is still moderately replicable w.r.t. Hu.
Lemma 3.6 (Concentration of Acceptance Probabilities). Let & E (0,e) and A be a deterministic tester that is log -2 re-repicaable with respect to Hy. Assume that m o(ne Then it holds
1 Pr (Accm (p. A) - Eg'wMs [Accm (p'mmppp,44 [p]] > 1) S 2"
The formal proof is deferred to Appendix E.2. At high level, construct random walk on the sample space whose stationary distribution is the same as T ~ p. where p ~ MMe-
Definition 3.7 (Sample Random Walk). Let M be a meta-distribution over non-negative measures over [r)). and m E Z4.. The sample random walk RW m.M is defined on the graph whose vertex set is ND (where each vertex corresponds to a sample count vector T) and transitions (T1, T2) are defined by the conditional distribution of T2 given Ti induced by the joint distribution given by the following process: (1) Choose p ~ M. (2) Tí, T2 are sampled independently from PoiS(m, p). Moreover, for a sample count vector T, we denote by RWk (T)) the random variable representing the outcome after l steps of the random walk RW m.M from T. For a non-negative measure p over [n), we denote by RWk m.M
(p) the distribution of RWk (T)), where T PoiS(m, p).
For simplicity, we write RW RWm,5 m.g RW M, where MM is the mett-distribution given in Defini- tion 3.2. The random walk turns out to mix very rapidly.
Lemma 3.8. Let & E0, and m o(n==2) 2). Then RW m.g has mixing time T() (llg((n66))
The proof is deferred to Appendix E.2. To see that the random walk is fast mixing, we observe that RW,, m. is product of n independent random walks induced by the following process on the sample counts & to E N for each domain element: 1) choose > ~ u(12+ == (1 - () X_ == (1- ())))

---

and 2) f1, 22 are sampled independently from PoiS(m, A). We show that the total variation distance between (miS(m. X+) and (oiS(m, X_) is not too large, so that most initial states t are about as equally likely to be generated by PoiS(m, X-) as to be generated by PoiS(m, X-). Consequently, the distribution of X conditioned on 1 will be close to the uniform distribution over A4, further implying that the conditional distribution of the next state l2 will be close to the stationary distribution.
The fast mixing time of the random walk then allows us approximate the polylog(n). As re-
stationary distribution by RW m.g( for some k sult, we can write Er (rsssssm [A(T)] - Ep [Er-pus(mpp)) [A(T)]]
R
m.c (p) [A(T)] Since A is replicable with respect to Hv. we can use the triangle inequality and some simple algebraic manipulation further bound the above by the sum of the terms
pp)ssm))pp)) [A(T)] Rw,
Pr T~ (p). (P). TW. (p)
(A(T) + A(T)))
where i E [k:. While it is challenging to establish a uniform bound on the terms for an arbitrary non- negative measure p. it turns out that this is not so hard for an "average" p MM. At a high level, if we consider the expected value of the disagreement probability in Equation (2) over
MMe, the term
simplifies Pry=me.T"ooy Tw.."""WW.mm. (2) [A(T) A A(T") PTp--Me.T Mr.T.... Poi'mm)) [A(T) A A(T") where the equality follows from the definition of the stationary distribution Tig of the random walk.
Therefore, the expected value of the disagreement probability cannot be too large as long as the tester A is still moderately replicable with respect to Hy. The formal statement is given below, and the proof deferred to Appendix F.3.
Lemma 3.9 (Indistinuushaabiiity of Random Walk Step). Let A be a deterministic uniformity tester and p MM. Define K := TTT"
[A(T) # A(T With probability at least 1/2, holds that Σi=1 PrT-RW m.t (P). TW- (T) (A(T) + A(T)) < 2kk, where the randomness is over choice of MM..
The proof of Lemma 3.6 then largely follows from Lemmas 3.8 and 3.9. After that, the proof of Proposition 3.4 follows from Lemmas 3.5 and 3.6. See Appendix E.4 for the formal arguments.
Acknowledgments and Disclosure of Funding
Ilias Diakonikolas and Jingyi Gao are supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. Daniel Kane and Sihan Liu are supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). Christopher Ye is supported by NSF Medium Award AF-2212136 and HDR TRIPODS Phase grant 2217058 (EnCORE Institute).
References
Acharya, H. Das, A. Jafarpour, A. Orlitsky, and S. Pan. Competitive closeness testing. Journal of Machine Learning Research- Proceedings Track, 19:47-68, 2011. 1
J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems, 28, 2015.
J. Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. Advances in Neural Information Processing Systems, 31, 2018. 1
M. Aliakbarpour, Diakonikolas, and R. Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In International Conference on Machine Learning, pages 169-178. PMLR, 2018.
M. Aliakbarpour, I. Diakonikolas, D. Kane, and R. Rubinfeld. Private testing of distributions via sample permutations. Advances in Neural Information Processing Systems, 32, 2019. 1, 1.2
T. Batu, L. Fortnow, R. Rubinfeld, W. Smith, and P. White. Testing that distributions are close, In st Annual Symposium on Foundations of Computer Science, 2000. 1
10

---

T. Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 442 451. IEFE, 2001.
Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating entropy. In ACM Symposium on Theory of Computing, pages 678-687, 2002. 1
Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal
distributions. In ACM Symposium on Theory of Computing, pages 381-390, 2004.
Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1): 2013.
M. Bun, M. Gaboardi, M. Hopkins, R. Impagliazzo, R. Lei, T. Pitassi, S. Sivakumar, and Sorrell. Stability is stable: Connections between replicabilityy privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pages 520-527. org/10 10. 1145/3566244.
ACM, 2023a. doi: 10. 10.1145/3564246.558544 3585246.
URL
M. Bun, M. Gaboardi, M. Hopkins, R. Impagliazzo. R. Lei, T. Pitassi, S. Sivakumar, and J. Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pages 520-521 200-527,55 2023b.
B. Cai, C. Daskalakis, and G. Kamath. Priv'it: Private and sample efficient identity testing. In International Conference on Machine Learning, pages 635-644, PMLR, 2017. 1
C. Canonne. A short note poisson tail bounds, 2019. URL https::
com/ coanonne/ pdf. A.1
C. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends@ in Communications and Information Theory, 19(6):1032-1195 2022.
C. L. Canonne. A survey distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020.
C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing bayesian networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 370-448, 2017.
C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing conditional independence of discrete distributions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 735-748. ACM, 2018. doi: 10.1 44555/511745533
URL https: : //ooi.//i//// org/10 10. 1.0...11100 1145/3188745 31887566.
C. Canonne, Diakonikolas, D. M. Kane, and S. Liu. Near-optimal bounds for testing histogram distributions. CoRR. abs/2207.06596 2022a. doi: A2..500 20666669.. URL https: //doi. //doi.org//i org/10. 0tgg/1.485550 40.50/850050 11850/arXiv.. wrw.a.avvvv........ 2207 06596. Conference version NeurIPS'22. 1
C. L. Canonne, A. Jain, G. Kamath, and J. Li. The price of tolerance in distribution testing. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 573-624 PMLR, 2022b. 1
S. Chan, I. Diakonikolas, P. Valiant, and G. Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium Discrete algorithms, pages 1193-1203. SIAM, 2014. 1.2
Z. Chase, B. Chornomaz, S. Moran, and A. Yehudayoff. Local borsuk-ulam, stability, and replicability. arXiv preprint 1.X15:2311.01599, 2023.
C. Daskalakis, N. Dikkala, and G. Kamath. Testing ising models. In Proceedings of the Twenty-Ninth Annual ACM-SIAN Symposium on Discrete Algorithms, SODA 2018, 2018, pages 1989-2007. SIAM, 2018.
11

---

1. Diakonikolas and D. M. Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694. IEEE, 2016. 1, 1.2,
1. Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1183-1202. IEEE, 2015.
I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Sample-optimal identity testing with high probability. 45th International Colloquium on Automata, Languages, and Preeeroo Programming (ICALP 2018), pages 41-1. Schloss Degstuhl-Leciniz--eentie
für Informatik, 2018. 1.1
I. Diakonikolas, T. Gouleakis, D. M. Kane, J. Peebles, and E. Price. Optimal testing of discrete distributions with high probability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 542-555, 2021. 1.1, 2, 1.2, 2, 2, 2, 2.5, 2, 2.10, C, C.I, C.2
E. Eaton, M. Hussing, M. Kearns, and J. Sorrell. Replicable reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
H. Esfandiari, A. Kalavasis, K. A, A. Krause, Mirrokni, and G. Velegkas. Replicable bandits. arXiv preprini arXiv:2210.011800 2022.
H. Esfandiari, A. Karbasi, V. Mirrokni, G. Velegkas, and F. Zhou. Replicable clustering. Advances in Neural Information Processing Systems, 36:39277-39320, 2023.
O. Goldreich and Ron. On testing expansion in bounded-degree graphs. Studies Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 68-75, 2011.
V. Guruswami. Rapidly mixing markov chains: comparison of techniques (A survey). CoRR, fbss/1603.01522 2016. URL http::///// htap:://aariiii org/ aa//ab/s/10000 01512. A.2
M. Hopkins, R. Impagliazzo, D. Kane, S. Liu, and C. Ye. Replicability in high dimensional statistics. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-8. IEEE, 2024.
R. Impagliazzo, R. Lei, T. Pitassi, and J. Sorrell. Reproducibility in learning. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pages 818-831, 2022. 1, 3,
A. Kalavasis, A. Karbasi, Moran, and G. Velegkas. Statistical indistinguishabiiity of learning algorithms. In International Conference on Machine Learning, ICML, 2023.
A. Kalavasis, A. Karbasi, K. G. Larsen, G. Velegkas, and F. Zhou. Replicable learning of large-margin halfspaces. Forty-first International Conference on Machine Learning, 2024.
A. Karbasi, G. Velegkas, L. Yang, and F. Zhou. Replicability in reinforcement learning. Advances in Neural Information Processing Systems, 36:74702-74735, 2023.
R. Levi, D. Ron, and R. Rubinfeld. Testing properties of collections of distributions. In ICS, pages 179-194, 2011.
D. Levin, Y. Peres, and E. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2006. htttpss//pagssssssssssssssssssst E.2
-aw......................... A.2, A.10,
Liu and C. Ye. Replicable uniformity testing. Advances in Neural Information Processing Systems, 37:32039-3200 32075, 2024. 1, 1.1, 3,
S. Moran, H. Schefler, and J. Shafer. The bayesian stability zoo. CoRR, abs/2310. 2023. doi: 10.48550/ARXIV.23110 18428. URL httpp:://dot org/10. 1tt1110..8550// arxiv 2310 18428.
Paninski. coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions Information Theory, 54(10)::750-44555 2008.
12

---

R. Rubinfeld. Taming big probability distributions. XRDS: Crossroads, The ACM Magazine for Students, 19(1224--28, 2012.
G. Valiant and Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing, 46(1):429-4555 2017.
P. Valiant. Testing symmetric properties of distributions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 383-392, 2008. 1, 1.2
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The abstract and introduction concisely demonstrate contributions and
scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Justification: Our new lower bound framework for replicable distribution testing does not require additional assumptions testers. Our replicable closeness tester with near-optimal sample complexity runs in linear time in sample size, yet our replicable independence tester runs in polynomial time in sample size. and wonder whether one can obtain a more efficient linear time algorithm. We discuss this in our paper. Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations"" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]
14

---

Justification: All assumptions were clearly provided in the statements and each statement has a corresponding proof in either the main body or appendix. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)? Answer: [NA]
Question:
Justification: The paper does not include experiments. Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper does not include experiments requiring code.
15

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
public/ heellii//uieess./
itt.sammissiooooooiooooooiiiiiii plycc) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //nips
http//uw/e////eee//ee /Ct//eSuusmmiiiiiccccceeeeeeieee aassonoiicyyyy for more details. httpc/gguudeeeoeeuuuubiieeeeee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments. Guidelines:
The answer NA means that the paper does not include experiments. The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them. The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
16

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neurbb: httpp//www.....ppoppeeeeeeeeeeee cccppullic/Bthicsuuul del ines?
Answer:
[Yes]
Justification: Yes. the research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid-
cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes]
Justification: While the paper focuses on foundational research, replicable distribution testing is aimed towards building an algorithmic framework for replicability in scientific analysis, helping build an efficient procedure verify experimental procedures are followed correctly and building public trust in science. The authors are not aware of any potential negative impacts. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
17

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: The paper poses no such risks. Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets. Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that re- papckaggdd, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
18

---

14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve L.MMs any important, original, non-standard components. Please refer to our L.M policy (https: : //wp///nn..////// tteeurips.cc/ooffeeeeee sccCoonferences/22255 22LL/LL222/ for what should should not be described.
19

---

Supplementary Material
A Additional Preliminaries
A.1 Probability and Information Theory
In this subsection, we present some basic lemmas about probability and information theory.
Lemma A.1 (Poisson Concentration (see e.g. Canonne [2019]). Let X Poi (A). Then for any x 0,
max(Pr(X 2 A 2), 5 x)) < I[++X)
Claim A.2 (Asymptotic Upper Bound of Mutual Information). Let X be an unbiased uniform random bit, and M be discrete random variable s.t. Pr[M alX 0] = (1) Pr[M al for all a within the support of M, then the mutuall information between the two random variables satisfies
that T(X: M) (1) E.
(Pr[M=a] PP Pr.M=a N
Proof. Denote = [r[M = a, X = := = 0, X 0 for simplicity. Since Pr[X
1] = Pr(X 0] = 1/2 = B = (()) then (8-a)² = θ (9-a)² = θ (B-a)²
By definition,
B+a
Pr[X 1,M a]
I(X = Σ
Pr[X = i, M = a] log
Pr[X = Pr|M = a)
1=
23 8+a
2a
Blog
+ aalog
3+
rearranging
1
= (1) Σ
3 log
+ a log
1+
a-8
1
a-8
23
2a
Denote A ; Q-8 23
and B- ==
8-3 2a
then by Taylor expansion of log
1+A
and log
1-B
1
we have
that
A"
B"
[(X : M) M)) 0(1) Σ
3
+ a
12
n=l n
1=1
= 0(1) Σ
Σ
Ba BA*) + Σ
33A" + aB²)
3m 21 odd
n=2
12 even
(aB" + -AA) < O(1)B Σo 0 ( (B a)²
(3=a)²
s 0(1) Σ 2 Σ
n=
as desired.
A.2 Random Walks
Let RW denote a random walk with transition matrix P where P(x, y) denotes the probability of transitioning to state y from state r. P((z, y) hence denotes the probability of landing in state after steps if one starts from state r. We give some elementary properties of random walks important to our analysis.
Definition A.3. A random walk RW is irreducible for all x. y, there exists O such that Pt (xxx)) y) > 0. Definition A.4. For given state x, T(x) == (t> 14>00 U.S. (((x, > 0}. The period of x the greatest common divisor of (2)). A random walk is aperiodic if the period of any of its states is 1.
20

---

A random walk that is both irreducible and aperiodic is called ergodic.
We say distribution
the states of random walk is stationary if it stays invariant after one step of the random walk. useful fact is that any ergodic random walk has a unique stationary distribution.
Fact 2. Any irreducible and aperiodic random walk has unique stationary distribution.
While any irreducible and aperiodic random walk guaranteed to converge to its stationary distribu- tion, interested in a quantitative bound on the convergence rate. In what follows, define the concept the mixing time of a random walk and give the relevant preliminaries (sce e.g. Levin et al. [2006], Guruswami [2016] for detailed survey).
Definition A.5. The mixing time r() of an ergodic random walk RW with stationary distribution defined by
T())
max min sE
S.S. (AV' 2 21)
Σ JEN
P/ Tzl {
We require the following facts regarding mixing time. First, the mixing time of a product random walk can be bounded via the mixing times of the individual coordinates (up to polynomial factors in the dimension).
Lemma A.6. Let RW be a random walk over the product space X", where the i-th coordinate follows an independent random walk RW; over X. Assume that RW; has mixing time (8)) Then the mixing time of RW satisfies that T (8) S max; (88/)).
Proof. Let p(1) denote the transition matrix for each coordinate and (1() denote the stationary distribution. Then,
m
II
play
n
(
S
p(e x(0)
This concludes the proof Lemma A.6.
For any ergodic random walk RW with transition matrix P and stationary distribution we let denote the eigenvalues of P. The following lemma relates the mixing time to the absolute spectral gap X, of the transition matrix (or alternative the relaxation time of the random walk).
Definition A.7. Let & be the set of eigenvalues of the transition matrix P. Xx, where max [ s.t. X + 1 and
The absolute spectral gap of
Markov chain with transition matrix "
Definition A.8. The relaxation time of a Markov chain trel
Another property important the mixing time of the random walk is the detailed balance criteria. If random walk satisfies this criteria, then we say it is reversible.
Definition A.9 (Detailed Balance Criteria). A random walk reversible if and only for all states F. x P(x v) T (())
We are now ready to state the mixing time of a Markov chain in terms of its relaxation time (or the inverse of the absolute spectral gap).
Theorem A.10 (Theorem 12.5 of Levin et al. [2006]). For ergodic and reversible Markov chain, its mixing time satisfies that
T(6) 2 (frel 1) log(1/28).
B Replicable Independence Testing Algorithm
In this section, we provide omitted proofs and analysis for our replicable independence tester, and then conclude the proof of Theorem 1.6.
We begin with a useful property of the flattening procedure (see Definition 2.1) it ensures that there will be no "heavy" bins after the operation with high probability.
21

---

Lemma B.1. Let S be a set of samples over [n] with |S| = poly (n), and S = Flatten (S; a.). Denote by Tt the sample count vector of the flattened samples. For any constant C, holds that Tí S 50(ps (a= logn) for all E supp (5t) with probability at least 1 - n -C where the randomness is over the internal randomness of Flatten(-).
Proof. After sorting the samples in S, we note that the position of the first flattening sample follows exactly geometric distribution with mean 1/0. Denote by Y its position. We have that Pr[Y > [= -1-1a (1-a)) Pr[y 2 aa log(n)] S n- for any number >> 0. This shows that with probability at least n- it holds that the number samples falling in the first bin is at most ax- a log(1/n) If we choose to be sufficiently large constant,
exp ((t-1) 1) log(1 - a)) S exp (=a(t 1)). In particular, this implies that
then have that Y I 0 lo(=nn))()) with probability least 1- 1-1/ 1/poly(n). Since Y is also the number of samples within the first sub-bin, Lemma B. then follows applying this argument to all subsequent samples and the union bound.
Recall that key technical step is bound the variance of the averaged independence statistic Zo (Sp. S,) by the expected value of the non-singleton sample count (a..p.
Proof of Lemma 2.9. We will bound the variance of (ap.p. S22) by the expected sum over samples of the squared difference the final test statistic by removing each sample.
In particular, suppose that Sp, S, contains the samples (Pr)ě=ı. For convenience, we denote by Ep. S the corresponding set after removing the sample Pa. We then have the following inequality that bounds from above the variance.
Var Var 5,)] S O(1) E
Σ (Za (S S Zn (S S,))
(3)
where the randomness is over the samples. Fix some sample sets Sp, Sq. Consider the random variables Z = INDEPENDENCESTATS (Sp. Sq) and Z_ INDEPENDENCESTATS (S -q. We claim that it suffices for us to show that
E - E S (m1m2) No (a Sq),
(4)
where the expectation over the internal randomness of INDEPENDENCESTAAT. After that, taking expectation over the randomness of the samples on both sides of Equation (4) and combining it with Equation (3) then concludes the proof.
It then remains for us to show Equation (4). Recall that the tester first partitions the samples into flattening samples and testing samples randomly. We denote by 5%, S/ the flattened testing samples constructed in Line 3 from the original sample set Sp, Sq. and s// _ S the ones constructed from the leave-one-out sample sets Sp. -q
Denote by F7. FM {0, 1) the indicator variables of whether Pe is selected for row or column flattening purpose respectively (see Definition 2.2) while constructing S Sf. We then break into cases based on the values of F?" FVV
In the first case, we have that FT- = F²
= This suggests that the f-th sample is not selected as flattening sample. Hence, there exists flattened version of Pt, which denote by P//, within S are obtained by deleting exactly pf from S/ S/. There are then again two sub-cases. Either pf a singleton sample among S/,-USs 9.-E- In that case, we must have Mc(Sp.S = _c by Fact 1. Otherwise, we have L(S) S() - Z(S ( ((1) as the closeness test statistic is Lipchitz in its inputs. As result, follows that
S/ U S In this case, 5$ pp--r 5.
p. S.,,) S
1IZ = F = 011 E) EIN US
(5)
'If Ps & Sp, then Sp.-e Sp. and the same for Sq.
22

---

Next, consider the case that F and F 0. which happens with probability at most Ps min (n, (100m), 1/100). This suggests that the P: selected as row flattening sample. Denote by Ke the number of samples lying in the same row Pt. Consider the following coupling between ( (conditioned on F = 1 and F 0) and (S -. S -. (1)Pick random sub-row a (in the flattened domain) weighted by the total sample count of sub-row within -/ U.S u divided by Ke, (2) subdivide the sub-row into two sub-rows a1. 02. and (3) randomly assign the samples from to d1, 02. Denote by T; the total number of samples among S pp U S s within the sub-row i, and N₂ the corresponding non-singleton sample count. Note that if a flattened sample is a singleton sample among _ S then it remains singleton sample after the subdivision, and hence has no impact on the final closeness statistic. Therefore, such subdivision can change the final closeness statistic by at most N, On the other hand, the probability of the sub-row being selected and the sample being selected for flattening purpose is at most Ps T:/ Kg. Hence, the averaged statistic changes by at most
No Ke
])
(BiZ 1(F7 = 1, - 2 (())
Σ
II'
Visabrows of the off?
Summing over all l' such that Ps and P/ lie in the same row then gives that
Σ
[E 1 = F. 03] -| ((1) E²
Σ
NopoT Ti
/Ke.
Pt lies in the same row as Py
Lisub-rows of the row Pt
By Lemma B.I, we have that T3 is most (og(n))pz" with probability least 1/poly (n1). Besides, Σ Eissubrros of the ofp, NJ is always at most Kg. It then follows that
Σ
(EIZ 11F7 1, P2 -
Pt lies in the
Per
< Ollog 2 n) E
Σ
N
/K,
iisub-rows of the row ofPr
S 0log? n) E
Σ
N
Lisub-rows of the of
Note that the non-single sample count can only increase conditioned on that Pa is not selected for flattening, which happens with at least constant probability. As result, the expected number of non-singleton samples among S U 5f 9.-- is always at most constant factor of the expected number of non-singleton samples among S S Summing over all then gives that
1B = F. =1 0}} - E|Z-,)) < Oloog n1) E (VSS
(6)
This then concludes the analysis of the second case.
In the third case, assume that F. 0, F 1. Using an argument that is almost identical the second case, one can show that
k
(B = 0. = 13] E(Z < Olog? n2) E [N(S st)]
(7)
1=1
as this corresponds to the case when the k-th sample is chosen for column flattening.
Finally, for F F# = 1, we can use an argument that is almost identical to the second case to show that
E 11F7 = =
- Elz 1177
= = = < O(log* m1) E (N(S,,)))
23

---

It then follows from the triangle inequality that
B = = -11
00
Σ
= [2 1}1)²
* = -f = - = Ologg 2 L NN st
(8)
Combining the case analysis (Equations (5) to (8) then yields that
(B|z)- < Ologg RI)E [N( U ss]]] = O(log" 11) Sq).
This concludes the proof of Equation (4) as well as Lemma 2.9.
Recall that adhere two-stage testing strategy, where first test the size of the expected non-singleton sample count before computing the averaged independence statistics. In what follows, we provide the proof which bounds the variance of the averaged non-singleton sample count by its expected value.
Proof of Lemma 2.11. Denote by (SS, St)) the number of non-singleton samples among S U St/- Recall that the averaged non-singleton sample count Na (Sp, Sy) is simply E (S S()). where the randomness is over the flattened sample set s/, St. Similar to the closeness statistic (c( S . has the two following properties: (1) (S, - is invariant if one removes any singleton sample from Syf St and changes by if one removes a non-singleton sample. We note that these are the only two properties used in Lemma 2.9 to show that the variance of the averaged statistic Zu (Sp. 5g) can be bounded from above by Ollog" (minz)) (Sp. Sy)l- Hence, we can use the same argument to show that Var (Sp S,)] < O(log* (m)72)) (Sp.. Sq)], and this concludes the proof of Lemma 2.11.
We are now ready to show the full analysis of our replicable independence tester, and the proof of Theorem 1.6.
Proof of Theorem 1.6. Recall that the algorithm has two steps. In the first step, it verifies that the size of the expected value of the non-singleton sample count is not large by comparing Na Sg) with a random threshold. In the second step, it computes the averaged independence statistics Z, (Sp: Sq) with fresh samples, and compare with another appropriately chosen random threshold.
We first analyze the correctness and replicability of the first step. Let m be defined as in Line 1 of PNDEPENDENCESTATEE and Sp, S, be sample sets with size 100m. By Lemma 2. 2010, the expected number of non-singleton sample count [N, (Sp. S,)] at most CN max (m² (nn///(nnn)))))))n//)))())) m m/n2) for some constant Cx if the underlying distribution p is indeed product distribution. By Lemma 2. 11, we have that Var [Na (Sp, S,)] < IE (Sp S,).. We first show the validity of the following bound:
log (n;) max (m² (22), m/n2) < p² (max (m² (2f//(nnn)))))))) m/n2))²
In particular, we will see that for this step, it is sufficient if m > -nj n2 p 2/3 + vninop We begin with case analysis. In the first case, we have that m² m²/ (m)n))))) is the dominating term in Equation (9). is not hard to verify that
2/3 1/3
m² (11n2) S p²m (n1n2)²
as long as m >> Vnjnipp11 So Equation (9) easily holds this case. In the second case, we have that m² ((nni))) & m/nz and so m/nz is the dominating term. In this case, we need to show that m/na S (m 22 which is true as long m 2 n2 In particular, the case assumption
24

---

indicates that 11 112 p 2/3 1/3 22233 & m < R1. This implies that n4 >> nzp02 which further implies that
m > /minzp" > n2p 2. This hence concludes the proof of Equation (9).
To argue the correctness of the tester, we analyze the completeness and the soundness cases separately, Denote by G :==Ca ON max (m²/ (nnn2), m//2).. In the completeness case, the expectation is at most G, and the variance is at most (1) log" 2 [m: ).. By Chebyshev's 's inequality and Equation (9), the statistic (Sp: Sq) will be at most 2G with high constant probability. In the soundness case, suppose [No sq) 2 101G. It not hard to verify that G > (m11 as our choice of m ensures that m > log (m1) 2 log" 2 (m1) )mg. In particular, this implics that vlog(n1)G < G. In this case, by Chebyshev's inequality, Naa (Sp, S.y) is at least 101G - / log" (n1) 2 100G. The above ensures that the tester will be correct with high constant probability. Combining this with the standard median trick then ensures correctness with probability at least 1 - p at the cost of increasing the sample complexity by an extra (1g(1/p) factor.
To argue the replicability of the tester when we are in neither the completeness nor the soundness case, we note that the variance is at most Iog(n; G) By Chebyshev's 's inequality and Equation (9), we have that the test statistic will concentration around an interval of size Vlog (n ) & pG with high constant probability. Again, combining this with the median trick ensures that Na S,) will lie in an interval (around its expected value) of size pG with probability at least of increasing the sample complexity by an extra factor of log(1/p)). Conditioned on that, we have that the tester will be replicable as long as the random threshold lies outside this interval of size pG, which happens with probability at least 1 p. We can therefore conclude that the tester is replicable with probability at least 2p by the union bound.
p (at the cost
Conditioned on that the first-stage testing passes, we hence must have that
Var (Sp. & (m1) (Sp, S,)] O (log² (m² ((1122)))))))))))))()())))))(() + m/n2).
Besides, since Zu (Sp. S,y) is the average over some statistic that is Lipchitz in the input samples, we also have the trivial variance bound Var (S,. S,)l < ((m). Again, we begin with a quantitative bound that will be useful for both the replicability and correctness analysis:
V (n;) min(m, m2 (m))2)))))))))))))))))())) + m/n2) < p min (em, m²=? ( m3/2 Vmnaa). (10)
Again, we proceed by a case analysis. Suppose the right hand side evaluates to Em. We note that log(n)) mmm < pem as long case. Suppose that the right hand side evaluates to (m)12)))) The case assumption implies that m 1/2 I /ning, which further implics that m S 12 122.2. Since we always have m >> 72, this suggests that m/nz will be the dominating term on the left hand side. However,
>> log (n -2_ So Equation (10) clearly holds in this
always have nn2 "022p= -//33 This verifies //
log(n;) /m/nz/////// < pm3²=/ / ((11))) as long as m >> log2/((m,, (m1)m 2/3 1/3
the validity of Equation (10) in this case. The last case is when the right hand side evaluates to m 3/2/2// /ming. In this case, it suffices to show that log(n) (Mmmmmmmmmmmmmmmmmmm < pm3/22² 22 ///n// which is true as long as m >> log(n1) ( - pp- This concludes the proof of Equation (10).
To argue the correctness of the second stage, we again break into the completeness and the soundness cases. For convenience, denote by Hg min (sm,m?? m²=²/ (2////(11)))))))/ n///222/ /T1nz)) and Hy := log" (ng) min(m. (,. m² m²/ (2) + +m/n2). In the completeness case, by Lemma 2.5, we have that ([Za Sp. Sq) < Cr, H By Equation (10) and Chebyshev's inequality, we have that 2a (Sp. S,)) S C₁, HE + O (VHv) < (Cr, + o1)) HE with high constant probability. In the soundness case, by Lemma 2.5, we have that (S S,) 2 Ct2 Hg. By Equation (10) and Chebyshev's 's inequality, < (Cr, - -(1)) HE with high constant probability. This shows that the test on (Sp, S,)) is correct with high constant probability. Combining this with the median trick ensures correctness with probability least 1 p the cost of increasing the sample complexity by an extra factor of lp))
we have that (S,, S,) 2 Ct HE 00-0
To argue the replicability of the second stage, we note that (S S,) must lie in an interval around its expected value with size at most VHv & pHf with high constant probability. Again, combining this with the median trick ensures that Z, (Sp must lie in an interval I. of size pH with probability at least 1 p (at the cost of increasing the sample complexity by an extra factor of
25

---

log(1/p)). Thus, the tester will be replicable as long the random threshold chosen uniformly random from [C1, HR Cr H falls outside of this interval L. This happens with probability least pHg 1 [C12-Ur, 1 -1-00 O(p). We can then conclude that the tester replicable with probability at least 1 O(p) by the union bound.
Lastly, is clear from the description of REPINDEPENDENCESSTATS that the tester draws (m) many samples, and (Line 1 of INDEPENDENCESTATS) is within the sample budget of Theorem 1.6. This concludes the proof Theorem 1.6.
C Replicable Closeness Testing Algorithm
In this section, we present replicable closeness tester with optimal sample complexity.
Algorithm 3 KEICLOSSENSSTTSSTER((P..))
Input: sample access to distribution and q supported on [n). Parameter: E (0, 1/4) tolerance, E (0, 1/4) replicability, n support size.
Output: ACCEPT if p q. REJECT if drv (p. q) 2 6.
1: m -
2/8
+ y'
pp"
(mp: mmg mg: ml4) t Multinom 4m, 1/441/1))
2: Draw two multisets D1, D2 of iid samples from p of sizes mp, my, respectively; and two multisets
D3, D4 of fid samples from p of sizes my, my respectively. vi [n] let X,, X Y,, Y be the
occurrence of i in DI. D2, D3. D4, respectively.
3: Compute the statistic Vi [n]] Zi + X, 1i-Yy Yil |X! Y/1 X X
Y
Y and
Z + ii=1 Zz-
4: Set threshold r + Clym + To (R Clym) where +- Uniff {. 4.4) 2) and R, C are given in Lemma C.I.
5: return ACCEPT if Z S REJECT otherwise.
To show Theorem 1.5, the key idea is that firstly, to guarantee correctness the threshold we randomly picked needs to fall between an upper bound on the test statistic of the completeness case and lower bound on the test statistic of the soundness case whp and the proof follows from Diakonikolas et al. [2021]; secondly, to guarantee replicability we need to further make sure that the randomly picked threshold falls in the high confidence interval of the statistic with probability < p. so that upon multiple runs, the algorithm gives same answers whp. Remark that the main difference between replicable closeness tester and high confidence closeness tester is that the former needs to whp output the same result upon receiving different sample set even in the case when 0 < drv (p. q) < c, yet there's requirement on the behavior of the latter in such case.
The main ingredients are the two following facts: a concentration bound on statistic Z and the expectation gap between the case when p q and the case when drv (p, q) 2 Luckily, both facts were shown in Diakonikolas et [2021].
Lemma C.1. (Expectation Gap, Lemma 3.3 in Diakonikolas et al. [2021]) Given m, e, P. n, as specified in Algorithm 3, there exists universal constants C1, C22 >> 0 s.f.
E[2] S Civm; 1f = q
If d 2 e, E R
C2 min em, m² 3//222 n1/2
In particular, R >
C2ymmog(11p)
Lemma C.2. (Concentration bound Z, Section 3.2 in Diakonikolas et al. [2021]) Given m, P as specified in Algorithm 3, there exists a universal constant C 0 such that Pr 1Z - E [Z] C log(/p)) where C.m m log(1/p)
(C2v (C2/m//l(1/p)) C1 Civm
We are now ready show the proof of Theorem 1.5.
26

---

Proof of Theorem 1.5. We first argue the correctness. From Lemma C.I and Lemma C.2, with probability 2 1 p/2 threshold falls between the value of Z for the completeness case and the soundness case, whence successfully separates two cases,
We next show replicability. We break into 3 cases based on the value of R. Essentially we need to show that for each case the ratio concentration bound
expectation gup
When R C2EM, since m
36(2C+C1/0)
log(1/p) cpp"
we have that
20 (CV/log((// Czem
I
2
C2
C1 mm
6
When R = C2 ?
since m
4(20+C,/0)
log 11
e1/pp/3 we have that
20 m log(1/p)
m² C2
-Civ
6
7
When R = C2
m 2
nt/2 since (12C+C//6)
log
(1/D)/ pc
we have that
V m log(1/p)
C22
3/2,2 -Civm
n²/2
By union bound, Algorithm 3 is p-replicable.
D Poissonization and Internal Randomness Elimination
Let A be a replicable tester that satisfies the correctness requirement of the corresponding testing problem. To show sample complexity lower bound against A, we often construct meta-distribution B3 parametrized by a positive number & E [0, E] over potential testing instances. In particular, B3 will be constructed such that Bo represents a collection of instances satisfying the property to be tested while B, represents ones that are "far" from satisfying the property.
Our end goal is to show that A cannot be p-replicable under random choice of p BE, where É ~ e)), with non-trivial probability.
There are two common techniques towards the goal. Firstly, the tester is usually assumed to take fixed number of samples from a probability distribution. Nonetheless, a common practice in distribution testing is to first show lower bounds in the so-called Poisson sampling model, which allows for the more general sampling process for pseudo-distributions, i.e., non-negative measures over the discrete domain, and is often more amenable to analyze. After that, one can use reduction- based argument to translate the lower bound back to the standard sampling model.
Definition D.1 (Poisson Sampling). Given non-negative measure p over [n] and an integer m, the Poisson sampling model samples number m' Poi (m |pll)). ). and draws m' samples from p/ e/Ippll1 Define T E IR" to be the random vector where T; counts the number of element seen. We write PoiS(m, p) to denote the distribution of the random vector T. We say A is a Poissonized tester with sample complexity if takes input a sample count vector T ~ PoiS(m,,)) p).
Secondly, the tester A is in general allowed to use internal randomness. Yet, since have already fixed the hard instance meta-distribution over the testing instances, a common approach in showing replicability lower bounds is to use a minimax style argument that allows us to fix a "good" random string r such that the induced deterministic algorithm A(;r) enjoys about the same correctness and replicability guarantees under the meta-distribution as the original randomized algorithm. This then allows us to focus on analyzing the replicability of deterministic algorithms under ~ Be. To facilitate the discussion of the minimax argument, we introduce the notion of distributional correctness and replicability.
Definition D.2 (Distributional Correctness/Rellicchittt).... Let Bo, Be, H be meta-distributions over non-negative measures over [n]. Let A be Poissonized tester with sample complexity m.
We say A is 5-correct with respect to By and B. if Pi..p--BB. (A(T) = Accepd 2 2--6 8
and Pry.p=B., B..-B..TT-BB PPPSSmm)p))) [A(T) = Accept) <
We say A p-replicable with respect to 'H if holds that Pip-:H.,,." (A(Tm p.
(A(T) + A(T')) S
The notions of distributional correctnees/eeplicabllty for a noi--Piiso tester taking m samples (|1)))00 )mm instead of ~ PoiS(m, p).
defined similarly with the sampling process S ~ (p/l|p||aa
To make our lower bound arguments more modular, we prove the following meta-lemma that allows us to focus on lower bounds against deterministic algorithm within the Poisson sampling model.
27

---

Lemma D.3. Let Be be a meta- parametrized by a number & E E0, H. be meta- distribution. Both B& and H. are over non-negative measures p over a finite universe X satisfying |pll E (0.5. Let 6,p p E (0, 1/3), and m. be a positive integer satisfying 2 log(10/0) log(10/p). Consider the following two statements:
For any deterministic Poissonized tester A with sample complexity m, if AAA. is d-correct with respect to Bo and Be, then A cannot be p-replicable with respect to H.
For any randomized tester A that consumes m' S mm/1 samples over X, if A is 5/ 0/10-correct with respect to Bo and Be, then A cannot be pf 10-replicable with respect to H.
The first statement implies the second statement.
Proof. Let A be a randomized tester that consumes m' samples. Consider the negation of the second statement. particular, assume that is 8/10-correct with respect B, and Bg as well as p/10 replicable with respect to H. We show that this will contradict the first statement.
By Markov's inequality, with probability at least 2/3 over the choice of the random string r, we have that the induced deterministic tester ((;r) is 0.36-correct with respect to Bo and B.. Similarly, with probability at least 2/3 over the choice of r. A(: r) 0.3p-replicable with respect H. By the union bound, with probability at least 1/3 over the choice of r, A(;r) is at the same time O.pp-replicable with respect to H. and 0.36-correct with respect to Bg and Bg.
We will now convert the tester into a Poissonized one. In particular, consider the Poissonized tester A obtained as follows. We first take k ~ Poi(m) samples from the underlying distribution p/||p pll1- If 2 m', we take the first l samples, and feed it to A(:r). If k < m', we simply return reject. Since assume ||p|| E (0.5,2) and 2 log(10/5
log(10/p) p). ,) it then follows from standard Poisson concentration that k 2 m with probability at least 1 min(d, p). In particular, this implies that Á is a Poissonized tester with sample complexity that is the same time 0.Ap-replicable w.r.t. H and 0.46-correct with respect to Bo and B.. This therefore contradicts the first statement of the lemma.
E Omitted Proofs for Replicable Uniformity Testing Lower Bounds
In this section, we provide the omitted proofs for replicable uniformity testing. We give the proofs of Lemma 3.5, Lemma 3.9, Lemma 3.6, Proposition 3.4, and finally Theorem 1.3. Remark that since in Section 3 we assumed that @(vTTe 22p dominates e 22p-? throughout this section we have the implicit upper bound V = ō (ne-2).
E.1 Bounding the Average Acceptance Probability for Uniformity Testing
In this subsection, we provide the proof of Lemma 3.5.
At a high level, we appeal to the same argument as in Liu and Ye [2024] to analyze the expected acceptance probability of the tester. The framework proceeds as follows. Fix any cD < in [0, c] such that 6 co < cp. Let X be an unbiased random bit, P .Mex be defined as in Definition 3.2, and T ~ PoiS(mn. p) be defined as in Definition D.I. Then, the mutual information between X and T is bounded from above by a function of the parameters m, c, and p. as stated formally in Lemma E. Secondly, given the mutual information bound, we know that with limited amount of samples, for any pair of co. é1 e0. that are pe close to each other, I. Ep-M.. [Acc, (P. and Ep-M,, [Acem (p, A)] must be close to each other. See Lemma E.3 for the formal statement. Lastly, given A as above and is 0.1-correct w.r.t. Mo and Mg. then the acceptance probability function should satisfy that Ep-Mo. |Accm. A)] 0.9 and Aop-M,lAcc.n (p, A)] < 0.1. Thus, by the mean (Acc., (P, A)] 2. Furthermore, from the
value theorem there exists 5* E <0 such that Bp--M.. [Accm above Lipschitzness of E Ep--Me [Accm (p. A)] in & we know that for at least p fraction of [0, e], Ep-M, |Acc.. ()] E (1/3, 2/3), which concludes the proof of Lemma 3.5.
We begin by by showing the mutual information bound.
Lemma E.1 (Mutual Information Bound for Uniformity Testing Hard Instance). Let m o(ne-2 ling-2log- log-2 2n), 6o < E1 [0,e] be such that e co < ep. X be unbiased random bis,
28

---

Mex be the distribution over measures defined as in Definition 3.2. ~ MMxx T ~ PoiS(m. p). Then the mutual information [(X ...... , satisfies:
m² _ p² log n + t
T(X: T,, .T,) =0
n
Proof of Lemma E.I. Let 6 = 61 - -0 = O(ep). Since Mis are conditionally independent condi-
tioned on X, we have that
1(X Ti. TT)
((x : T.) n Ti).
Therefore, suffices show that [Xx: : Tı) = e+ log n) - (H).
We start by expanding the conditional probabilities of I conditioned on value of X.
Ti 0) Poi (m(1 (1 (1)) 2 n
Poi ( (= (1 co)
and similarly,
m (1 + (1+ + Poi
m (m (1)1-
71((X = 1) ~ Poi
2
n
then we can expand Pr(T] = a = and Pr(T, = a|X = 1] accordingly. Indeed,
a
(1 Ea) + 11 1
(o) exp (-m (1 En)
Pr[mi a|X 0]
+
6o
exp
(n)
2a!
71
a!!
n
m
exp
m
exp
med
(1 + c0) )a + exp
MMED
(1 - -00)))
2a!
m(co + 6)
im(E + 5)
Pr[Ti a|X 1]
exp
exp
(1+ co + 8) exp
(1 co 8)8
2a!
n
Since d- = o(E), Pr[Ti
a| 0 θ (Pr[T
alX = 1J) By Claim A.2, it suffices to show u²
that ī = E. X= = 0
nz A log n
+ +o (+)
Let
fa(y): = exp (-mm)
my n
(1 + y)
exp
my
(1 y)
(11)
Then it holds
01)
m
m (-m)
(Sa(eo) - fa + +8))²
0(1) Σ Ta
exp
a!
((o) + fa + +
0=0
where for simplicity, denote I, := m!
(eo) f.(eo++))) Then by the mean value theorem I, S fa(oo))
8 max S fv) whence bound la from above, suffices bound the denominator Falea)=fal (co++))
of RHS from below and the numerator of RHS from above separately. We next break into 3 cases
depending on the size of m.
Case 1: For the sublinear regime, i.c., < 1/2, we break into cases depending on the value of a.
when a = 0, applying the mean value theorem gives that (fo(eo) foleo + 5)1 S Since SolEa) + fo(e1) m=
m 8 2m)co+5) exp m()o+6) n
2(1), we have that To
O(1) (Joleo) - Soleo + 8))² =0
2g82) = - m2 n
2802 n
29

---

when a = 1,
[fi(E0) fi(Eo + 0)]
$ ( - fo + d)]
med
me0
) - (EO +6)
m(eo +8]
m(eo + 8)
+
c0
exp
- eep
exp
+ exp
n
n
n
n
m²
meg
ml(e + +0) )
mmee + 66)
meo
S 0
n2 500
+ exp
exp
+
exp
exp
n
m(co + 6)
m(Eo + +
+
exp
exp
n
n
m
=0
(the mean value theorem)
Combining with the fact that f1(50) + f1(E1) = 211), we have that I
O(1) (fi(c)) fi + +)))² o m² when a 2 2,
n² e²8²)
fa(y)
m
exp
my
(1+ + a(1 + 1) exp
(- my
dy
m my
exp
(1 - y) - a(1 y) exp
my
n
Before bounding By fa (v) we introduce a technical claim that is helpful in the rest of the proof to show the monotonicity of specific families of functions.
2
Claim E.2. For a, s, E R. when + dr 2 0, if dk 2 resp)))) + dz) then exp(a resp.) as a function xf x.
(s) + d is nondecreasing(nonincveaa
Proof of Claim E.2. 8 (exp(a bs + dx)+) = exp(a ba) d [dk: b(s + dz)], then
de
a if dk 2 b(s dr), we have that oe (exp(a - (s) + dr)²) 2 O. Similar argument applies when dk I b(s + dr).
When [ea, e0 + 5). by Claim E.2, since - 2 2 (1 y) m
fa(v)
I exp
(
my n
m ((1 +) (1 - ()m + ((1 + (1
By
17 I
a(1 + y) 2y + a(a () y) 2y = (22aay))
n
Thus, have that max Since fa(eo) + fa + +0) Q(1).
(g((()) max (0 0 (1"ate)
a m
I. < 0
a!
Since Ee 4"aa of converging series, it can be bounded by 0(1). Therefore, Eee Ta S
0) Dae m = 0
In conclusion, from the above three cases, i= 0 (
82)2 n
Case 2: For the superlinear regime when n/2 m
27 log" m we start by noticing that when
deviates far enough from m the sum of all such İ, is negligible. More specifically, let À m01-
30

---

and be constant such that exp 2(A+aa)
x²
1 then by Lemma A.1,
1x=elog n m/nn
(Pr[T] = a X = 0 Pr[ =a = 11)
1 11
Σ
Pr[Ti = a X 0] + Pr [ = 0 X
lotelog V m/n
as [S--olog mm/m m/n]
Therefore,
compute
suffices
consider La when a
A-clog clog ny m//mm, + clogny m/n Instead of directly bounding Ifa(co) fa(e1)l,
separate fy( into parts. In particular, by the Taylor expansion of exp(x)
[a( exp リリ y + a llog(1 + v)) + exp ( + log(1 - -v))
= + a log(1 1 1²2 +
(
m n
a log(1 + b) (= + a a - v) )))
1=
Define 9a = a aog((1 3²) and ha ha( = - 1/2 (- my + alog(1 + "))* Then follows that
fa(y) = 2 (v) + ha (1) hal ha(--)-
On one hand,
1-
1 2
Iga(co) - ga (c))) = alog
S a 1
(for x 2 1, [,/lo((>)| S x - 1)
1
1 1 c
a
(Eo + EI - E1l
1
0
eô log n
(12)
On the other hand,
ha (y)
a
Σ
(-
y + + + v) f-1
Oy
71
1 + y
(i - 1)! n
i=2
m
a
eepp (-- (1 y) -1).
y)a
71
1 +
When E [co, E1),
- (1 Eg - 6) + clog m/n
7
n1
1+ y
1 60 m
log nogny/ /
1 1+ y
1 1+
0(1) (" 6o + log / m/n O (logm nlonn// m/n)
n
where the last equality follows from the fact that v - o llggn
implies that log ny m/n > m. For eexp (1+ y)a 1/. from Claim E.2, since a m/n(1 (1 + y).
1
loga
exp my (1 + 1) nondecreasing and takes value when y = 0. Therefore, we can remove absolute value directly, which gives that
-m/1
m exp (-mh
(1 4)a - 1/ <
(1+
Σ
m/n 4)ah _
1=10
Dog ny m/nll
[Tlg n2 m/ni y
< 2(1 + y) hongn/m/nn - -1 1
[log n m/n)
ee log n m/n
< 0()
Σ
k
31

---

dominates the last term, it suffices to show that lolog lallon////r = o(1)
To show that O E log farymm//// m/n and only if m
Le. logn/m/n/
which is equivalent to showing that v /m/n o ((og lognee This is true if assumed in the premise.
log*
Therefore, we have that eaxoel have that
a by (v)) = 0 (e log m By the mean value theorem,
(Ea(E)) ho (e) 0 (eo (éllog* log n n=
(13)
and
Vha (-1) 0 log n m
(14)
n
Combining Equation EquatEqn (13),and Equation (14), we have that (Ea) fa(e:)] = - (cdlog log" )
(15)
We now consider bounding from below the denominator fa(eo) + fa(()) Recall that from Equa- tion (11), we have that
my fa( = exp (- mey (1+ + exp
(1 - y)"
n1
Since + x 2 exp(x x²), ) we have that
(1 + y)th 2 explay ag²²). This implies that
fa(Eo) + fa(e)) 2 (2(1) exp
(e 8) (- m + + - a(E + 8)3)
(1(1 exp
(-m (e 8)² (e + 8)c log / m/n ale + 8)2)
n
(111 exp
(-me log ny poggn/// m/n log ny m/n)
Since " ( (oog
o
we have that
1 exp(o(1)) (1)).
fa(co) fa(e) 2(1)
(16)
Hence, by Equation (15) and Equation (16),
2
(Sa(tu) fa + 8))²
= 0(1)
Σ
exp
m
a!
n
fa((n) + fa(Co + 8)
o 282 122 log n m²
Σ
m a!
m7
exp
+
n
n2
a2 l Atclog m/n/
2 log a m//] aE2
Since Σ [A 1--clog m/n
m
m al a
exp(m/n)), this term cancels out with the
a= u= log / m/n|
succeeding exp(-m/ term. Thus
I 1
(20 log n m²
202 202
1 7
+ 0
no
as desired.
The above 2 cases conclude the proof of Lemma E.I.
The second step of the framework is as follows.
32

---

Lemma E.3 (Lipschitzness of Expected Acceptance Probability), Assume that m Ö nne 20-2--p1 pp1). Let A be a deterministic tester that takes a sample-count vector over [nl] as input. Let co c [0,c] be such that 60 S ep. Then it holds that
P [Acem (P. A)] Ep... (P. < 0.1,
where Acem the acceptance probability function defined as Accm (P. Pry-ras((mp)) (A(T) = Accept].
Proof of Lemma E.3. Assume for the sake of contradiction that [Bp-Mc. [Acen (p, A)] Ep-M., [Acom (P.A)l 2 0.1. Let X be an unbiased random bit, and be the random variable defined as follows: let ~ MMx. T ~ PoiS(m, p). then Y =
=1 1 A(T) accept, Y == O otherwise.
It follows from the definition and the assumption that Pr[Y =| = I Pp (Pp-M.,lAAcmm.. (p,
and Pr[Y 1|X 1] Ep [Accm A)], which implies a mutual information bound of T(X : T) T(X Y) 9(1). This clearly contradicts the result from Lemma 1. and hence concludes the proof of Lemma E.3.
We are ready to show the main result of this subsection.
Proof of Lemma 3.5. Since A is 0.1-correct w.r.t Mo and M.. we have that 0.1. Furthermore, since Ep-MM Accem (P.A) is polynomial in E. it is continuous in &. Hence, by the mean value theorem, there exists E* E e0, such that Ep [Acom (P, = 1/2. It follows immediately from E.3 that Vg E 1s* 5 h- + pe] we have that
Ep-.Mo m p. A)] 2 0.9 and Ep-.M. A)]
Noo.M[AAco.. (p, E (E [Acem (p, A) 0.1, Ep-M [Acem (p. + 0.1)
= (..4.0.6) C 21/3,2/3).
In conclusion, if we uniformly at randomly select a E E [0, c). then once it falls in interval |g pe:5* pe] of length 2pe, which happens with probability 2pe, we have that Ep~Ms [Accm (p, 21/3,2/3) as desired.
E.2 Concentration of Acceptance Probability
In this subsection, we prove Lemma 3.6. Throughout this section we identify the Accept outcome with 1 so that Acc,. (p, A) Pit.-Pos(mmp)) [A(T) Accept] = Er-Poss(m.p) [A(())
key technical result this section to bound the mixing time of the random walk RW RW m.Me which we abbreviate as RW m.g within this section for convenience.
Lemma 3.8. Let E e0,e) and m o(n Then RW m.f has mixing time 7 (6) = O(log(n/6))) (6))
We analyze the transition probability of the random walk RW, m.g. We first note that drawing Poi (m) samples from MM is equivalent as drawing Poi (mp:) samples from each bucket independently where p; { 1+E 1-E] is the mass of bucket under the measure p. Since the observed count of n, n
each bucket i E [r]] is independent, we may decompose the random walk RW m, as a product of n independent random walks.
Definition E.4. The Coordinate Sample Random Walk RW m.g.i is defined on the graph whose vertex set is N and transitions [i) Ta(i) are defined by the conditional distribution Ty induced by the joint distribution given by the following process:
Tz [i] given [i]
1. Choose P Eu (1t.)
2. Ti T2(1) are sampled independently from PoiS(m, Pc).
Given sample count T[i,, we denote RW m.g.s (T(i)) the random variable representing the outcome after steps of random walk from T. For p. 2 O, we denote by Rw (p.)) the distribution of Rw e. (Tlil) where T[i] PoiS(m, p.).
33

---

By independence, we have that
RW
II RW m.g
For sample T. let T[ denote the empirical frequency of the i-th bucket in T. Let T₁ RW (T).) We can write the joint distribution Tp. T1 as
(c 1--mm(1425 (m)) (1++)m//n) /1)
+ e-2m(11-E)) ((1-))()))))))) (Q--)m/n)***+ /a)
a.bl
alb!
Pr(Toli] = a, ai]i =)
2
a+b
2m/n
25m// (1 E)ath + 22m//(1 - e
5)atb)
2a!b!
Furthermore, we have that
2(1++)mm/n ((+5)m/m)))t
te -2(1-g)m// [01 (1-$)m/n)"
alb!
a!b!
Pr(To]d] =
2
b=0
(1+E)m/m (m/m)mm))) + - e-(1-E)m/nn(1 mm//n)
2a!
1 -m/n (m)
(c (m/m// E) + cEm// 5)a (
2a!
Combining the two gives that the probability of the transition P(a. (T(TT b/Tb a)
P(a,b) Pr(Ti] [ = b, Told =
Pr[To[t] =a)
1 b!
m/n
m /
(-22m//(11 + g) 2 E)a+b <m//// + E)= efm/n {
This defines the random walk RW m.ç.i for each i E [n] with transition probabilities given above. Given RW m.g, for all i, we can write the transition probability of RW m.g from (a)..... an)
to b = (bi,... bn) as
Pr(RW, ma) b) II Pr [T
TT[d ai)
m b; e 25m/n + E) + 26m/n (1 -) a) e e-Im/n(1 g) cLm/n(1 g)
e
In particular, the stationary distribution of RW m,, is the vector æ E [m]" given by
T((a),... an))
Pr (T(To az)
1=1
m
(e (1+/ + cmm/m(1-))) 101--990
2ay!
It is not hard to see that random walk is ergodic and reversible.
Lemma E.5. The random walk RW m.g is ergodic and reversible.
34

---

Proof. The random walk RW m.g is ergodic since every transition is possible (including self-loops). Furthermore, RWm. m, is reversible since (ii)) is a joint distribution that is the same as T()))(
We proceed to show that RW m.g.j mixes rapidly. Lemma E.6. Suppose
") The random walk RW m.g. has mixing time r(0.04) 2.
Proof. Note that the random walk RW m.g. has transition probabilities from Yo 2 0 to Y 2 0 given by the conditional distribution induced by the following joint distribution.
1. Let X ~ U4(0, 1}) be uniformly random bit.
2. Independently sample Yo, X1 Poi (mm(1 - <)/n) if X and otherwise sample Yo, Y1 ~ Poi (m(1 + /)/n) if X
A useful fact is that the total variation distance between Poi (m(1 - 5)/n) and Poi (m(1 + f)/n) is small.
Claim E.7. Let A1 > d O. Let X ~ Poi (X1) and Y Poi (A2). Then
(A1 12)2
drv (XvY) <
222
Proof. We begin by bounding the KL-divergence as
t1
A1 11
(A1
2
DKL A log
A2
A1 A
+
\1
A2
A2
A2
where we have used log
< for O. Now, using Pinsker's inequality, bound
(A1 22)
drv (X,Y) <
2)2
This concludes the proof of Claim E.7.
We handle the sub-linear and super-linear cases separately.
Sub-linear Case: m E n. Note that Claim E.7 implics that the total variation distance between Zo (mi(mml1 {)/n) and Z1 Poi (m(1 + e)/n) is at most
(2mE/n)²
2m /n
< 25. 1 1-
2m(1
8)
where in the final inequality we have used m/n < and - >>> 0.5.
Now consider a step of the random walk from initial state Yo L. The distribution of Y; is given by the mixture of two Poisson distributions
Pr(Yi Y f) Pr(X 0/%, E) Pr(Zo k) Pr(X 1 6) Pr(Zi k).
The total variation distance between this distribution and the stationary distribution æ is at most
1 { < 25. 1 E1 |Pt(Y = k|1o 6) n (k)) < Pr(X 0|1o f)
2
Now, consider step from Y1 k. By the total variation distance bound, we can conclude that
an algorithm cannot distinguish X 0 with advantage better than 2 0.2. Therefore, we can bound 0.3 < Pr(X 0jYı k) < 0.7 otherwise the algorithm that returns X with this conditional probability distinguisher: From our previous calculation we conclude that after two steps, the
random walk mixes to within 0.4g < 0.04 of the stationary distribution.
35

---

Super-linear Case: S m o (3)) Following similar arguments as in the sub-linear case, the total variation distance between 70 7 is at most (1) < 0.1. As in the sub-linear case, no algorithm can distinguish X with advantage better than the total variation distance 0.1. Since Pr(X = 0 = k) < 0.6, we can conclude that the random walk mixes within 0.01 of the stationary distribution in two steps. This concludes the proof of Lemma E.6.
Given Lemma E.6, we can bound the relaxation time of each coordinate random walk via Theo- =(6)
+ 1. Combining this with rem A.10. In particular, we have that for RW m.g. frel S [og(1/26] Lemma E.6 gives that
T(0.04)
2
Leel
+15
+ +1= 0(1).
log(1/0.08)
log(1 (1/00)))8)
We are now ready to bound the mixing time of the product random walk RW m..-
Lemma E.8. Let m = o ) Let (()) ~ Poi ((1 + {)m/n) or (r((()))))))))))( ~ Poi ((1 - E)m/n) denote the initial distribution. Then, under either initial distribution y, RW m.g,s has mixing time:
(6) = ((log(1/)).
Proof. Consider coordinate random walk RW m,g.i- Let P denote the transition matrix and p denote transition matrix after steps. Let π denote stationary distribution. Recall that we have shown that RW m.g.i has constant relaxation time and therefore constant absolute spectral gap X Given either initial distribution 7(z). our goal is to bound the quantity
Σ E1(o))(a
(V))
We begin with the following inequality that follows from the proof of Theorem 12.5 of Levin et al. [2006]. For any two states x,
p (I, 4)
X
(1)
v=(z)=(V)
Multiplying both sides by (x) we obtain the inequality
\((=)
(xx)) {())<())) (0))))))))))))
V (T))
The next claim bounds the ratio between ((x) and π (xx).
Claim E.9, For any x 2 0,
((x) π xx)
< 2.
Proof. Let Zo ~ Poi [(1 m)//)) and Z1 ~ Poi ((1 + mm/)). Let λg A1 denote the means of Zo, Z1 respectively. First, we show that (x))/<(x)) is bounded when y Zo-
Pr x:)
Pr x)
(Pr(Zo P = x))/2
Pr(Zo x) Pr(Zi = x)
2 Pr x) =
Pr(Zo x)
similar argument holds for 7 ~ Zi. This concludes the proof of Claim E.9.
Continuing from our previous calculation, we obtain
(xx) (z)) X: (2(())))))
Summing over applying the triangle inequality and noting that Σx 7(x) = 1, we now have
Σ (()))(() m(t)
s X³ V
2T (3) Σ V7(x).
For the remainder of the proof, we will consider the sub-linear and super-lineat cases separately.
36

---

Sub-linear Case: m S n. Since m I n, in both cases the Poisson distribution has parameter (1++ 1.1. By standard Poisson concentration, for both E {0. 13
Pr(Z, x+ < - (/2((+))) Q(4)
In partieular, 7(x + 2) ((x) for all æ. Therefore,
8 Σ
O ( + E (
20
( Σ
Σ -200//2211)= ==C
for some large enough absolute constant C. Here, observe that for C, -2x222221111 < c =/C'' for some constant C' that the second term is infinite geometric series with ratio e 1. Similarly, we can bound Zy (V) O(1). Thus, to conclude we sum over y and note that
Σ Σ Ex(a) 7(y) V2 Σ Tly) Σ v)
In particular, from the initial distribution y, the random walk RWg mixes to in time ( (1)))).
Super-linear Case: n < m S ( Recall that æ, ~ Poi (Ai for À {(1 + 3)//n(C (1 {)m/n). Using standard Poisson concentration (e.g. Lemma A.1) and noting that À > 1- &. we observe that for any x, we have (xx (((e-A)) As in the sub-linear case, we begin by bounding
Σ / (x) for initial distribution 7. For sufficiently large constant C, we can bound
Vo(a)s S
E V*(z) 1z-A/5C
E (1x)=0(1) 18-A|30
As above, we observe that for large enough C, Σ N (()) can be decomposed into two geometric series with ratio strictly less than 1. Since a is a mixture of both 7, we have that Σ, (T( O(1) as well. The conclusion then follows as in the sub-linear case. This concludes the proof of Lemma E.8.
Proof of Lemma 3.8. The proof follows immediately from Lemma E.8 and Lemma A.6.
We are now ready to show that the acceptance probability of the algorithm on sample drawn from PoiS(m,, (m, p) for random p ~ MM well concentrated assuming that the algorithm is sufficiently replicable in terms of the mixing time of the random walk.
Lemma E. Let = (0.01) and & E [0, e). Suppose A is 10x- dx-rreplicbble with respect to Hy- Then,
1
1
Pr M-
ET [A(T)] Er [A(T')]
S
4
2
Proof. Consider the following sampling process:
1. Sample MM..
2. Sample To PoiS mm. p).
3. For 1 < k: < K = (0.01) O(log n). sample T. RW m. (TR-1).
From Lemma 3.9 we know that on average over p ~ Mg. A(Tp) = A(Ti) = A(Tk) with probability at least 0.9. By Markov's inequality, for I 2 ffacctio S, we have that A(Ta) = A(Ti) =
A(Ta) with probability least 0.8.
We now argue that the distribution of Ti is 0.01-close to the distribution 7f drawn from the stationary
distribution in total variation distance. Since RW... m.g is product random walk. Lemma A.6 implies that it suffices to argue that each coordinate random walk RW m.g.i mixes to within 0.01 of the stationary distribution on that coordinate in 7; (0.01 /n) steps. Fix a coordinate i. Note that T ~ Poi ((1 + m)//n) or Poi ((1 - f)m/n). In either case, the initial distribution satisfies the
37

---

assumptions of Lemma E.8, so that after Oloog n) steps, the random walk RW m.g,i mixes to within 0.01 of the stationary distribution. Given that 7kk is close to the stationary distribution, the data processing inequality says that the probability of acceptance under either distribution cannot differ by more than 0.01.
Here, recall that T is given by T' p where p MM. In particular, since the stationary distribution is exactly the probability of sample drawn from random ~ _Mg. we have that for -fraction of S,
E (pn.Me.(A(TT)) (A(Tb)) Brow (A(T")) Tomp
< EpnMe (A(To)) BT m. Tomp
(T6) (TO) (A(TR))
+
mis (To) (A(Tk)) ET (A(T))
2 0.2 + 0.01
1
4
We are now ready to prove the main lemma of this subsection.
Proof of Lemma 3.6. From Lemma 3.8 we note that the mixing time K = 700.01) = O(log n). Then, since we assume that A is (log n)) 2 with respect to Hv. have A is Tok replicable with respect to Hy. Applying Lemma E010, we obtain the desired result noting that Accm (p. ET-poi((m.p) (AT))
E.3 Random Walk Indistinguishability
In this subsection, we show that moderately replicable tester in general cannot distinguish sample from the outcome after one random walk step.
Proof of Lemma 3.9. We first show that
(A(T) # ACT'))
Pr M ()) RW (T)
< <kk,
(17)
After that, the lemma will follow from Markov's inequality.
Note that if we sample p MM. and then T PoiS(m, P), we obtain exactly the stationary
distribution of the random walk. Thus, the distribution of T (Wir((p). T' RW m. (P) is
equivalent p MM, T PoiS(m, p), T RW m. (T). ). If we focus just the joint distribution
of T,T", by the definition of RW m.g, this is the same as T ~ PoiS(m, p), where
Mg.
This therefore gives rise to the identity TE PP PrT~RW T"~ (A(T) + A(T')
PTp-Ms TTT [A(T) * A(T")] = K. Summingg over all i then concludes the proof of Equation (17) well as Lemma 3.9.
E.4 Lower Bound for Poissonized Tester and Proof Theorem 1.3
Proof of Proposition 3.4. By Lemma 3.5, with probability at least 2(p) over the choice of &, we have that
E Ep [Ace, (p. A)] (1/3, 2/3).
(18)
Conditioned on some & satisfying the above, we claim that we must have
(A(T) + A(T')) 2 log-22 n.
EpuMs
Pr
(19)
38

---

We will proceed by proof of contradiction. Assume that the opposite of Equation (19) holds. In that case, Lemma 3.6 becomes applicable, which gives that
[Aco (P.A) - Ep-Me [Acem (P] > 1/4 - 1/2. p~.M
Pr
(20)
Combining Equations (18) and (20) then gives that Acem(
(1/3 1/4, + 1/4)
with probability at least 1/2 when we choose p ~ MM.. Conditioned on such p. we 2(1). This therefore implies that Ep--M [Prr: p) [A(T) + A(TT]]] 2 9(1), which contradicts the assumption Ep-.Me (Prr.:rr-pis(mmppp) [A(T) # A(T"]]] I log (n)). This concludes the proof of Equation (19).
immediately have that Prr..rPoS(.ppil (A((T) # A(T")]
Recall that the meta-distribution Hy precisely the distribution of p one first chooses from [0, uniformly at random, and then chooses Mg. Thus, combining Equations (18) and (19) gives that
(A(T) * A(T')) 2 2lpp n)..
Pr P~N
Pr P.T
Moreover, ||p|| E (1 +)) (0.5, 2) with high probability. This therefore concludes the proof of Proposition 3.4.
Our lower bound for replicable uniformity test easily follows from Proposition 3.4, and Lemma D.3.
Proof of Theorem 1.3, Assume without loss of generality that m 2 log(100/ + log(10 log n/p). From Proposition 3.4, any deterministic Poissonized tester with sample complexity öl o(Vne-** p that is 0.1-correct with respect to Mo and Mr cannot be log -2 n-replicable with respect to Hy. Furthermore, any p ~ Hy satisfies ||P| | E (0.5, 2) with high probability. Thus, even conditioned on p Hy satisfying the norm condition, the deterministic Poissonized tester cannot be both 0. 1-correct and < plog -2 n-replicable. The conclusion therefore follows from Lemma D.3 (i.e. any randomized tester that 0.01-correct cannot be p/ e/polylog(n) b/pplyloo())-rrepiccabeeee replicable.
F Omitted Proofs for Replicable Closeness Testing Lower Bounds
In this section, we give a sample complexity lower bound of 2(n2/33 4/3p-213 e =-²p-²) ?) for replicable closeness testing.
2/3 + vns-22ppp
Note that closeness testing is at least as hard as uniformity testing (even when replicability of concern). Hence, it remains for us to show lower bound of Ω 2 4/3 4/3)-2/3). Note that this term dominates exactly in the sub-linear regime so it suffices to prove lower bound in the regime m <
We start by describing the hard instance for replicable closeness testing in this regime. In particular, construct meta meta-distribution over pairs of non-negative measures that will be used inputs the closeness testing problem.
Definition F.1 (Closeness Test Hard Instance). For & E [0, e). we define Ng to be the distribution over pairs of non-negative measures pę, q generated as follows: Vi [n]
I-c
W.P.
m0
m
2 26 2(n-m)
(i)
2(n-m)
W.p.
2m
(21)
26-5
2e+E 2(n-m)
2[
w.p.
The meta-distributie He the distribution over random pairs of non-negative measures (p. 9) generated follows: choose uniformly at random from [0, c). and return (p. q) Ng.
Again, thanks to Lemma D.3, after fixing the hard instance to be He. it then suffices for us to show sample complexity lower bounds against deterministic closeness tester A within the Poisson sampling model.
39

---

Proposition F.2. Let He be the meta- meta- distribbiti defined as in Definition F.I, A be a deterministic tester that takes as input a sample count vectors T N2n, and m o(n2/0g 4/3 2/3 + n). Then it holds
-2 n and || (p @ q) /2/1 (0.5, (0.5, 2) 2 p.
Pr (p.q)~HH
Pr (TTT"=-aSS(mpppe
(A(T) + A(T*) 2 log-
In the rest of the section, we focus on showing Proposition F.2.
Define Acem (p. q. == Pry-PooS(m.peq) [A(T) = Accept] Similar to the argument for replicable uniformity testing lower bound, we begin by showing the intermediate result that the average acceptance probability F(p.a)-NG [Accm (P, A)] is close to 1/2 with probability at least p if is chosen randomly from (0,e].
F1 Bounding the Average Acceptance Probability for Closeness Testing
We dedicate this section show the following lemma.
Lemma F.3 Let A be a deterministic Poissonized tester that's 0.1-correct w.r.t. Ng. then Pre-ac(O.E)) (E(P.g)~NG [Acem (p. q, A). E (133, 2 as long as m = o(n2/3g 4/3 10//3///33p000/ 2/3 n).
The argument again uses information theory and is similar to the proof of Lemma 3.5. We follow the road map similar the one to show Lemma 3.5 in Appendix E. where the main difference that we work with a different hard instance. We therefore present the needed lemmas without restating the outline.
Lemma F.4 (Mutual Information Bound for Closeness Testing Hard Instance). Let m < nn/2, < Ei E [0, e] be such that E E0 < Ep, X be an unbiased random bit, (p. q) _Nex be defined as Def- inition F.I, T PoiS(m, p q) in Proposition F22 where (TP: Tp. ......... ,TR T T 2..... T
E 2 where T.P counts the occurrences of element sammledd from p/ 1111, T counts the occurrences of element sampled from q/ 4/l9/11. Then
20mm n2
m3
1 (x: ... TP 1
= =0 x
I9)
pageppo e7p2)
Proof of Lemma F.4. Denote ô El ED O(p)). Since (Ti N:)s s are conditionally independent on X, we have that
I (x:
Tp TR.TA.
T S
X T.P.p. T,, =: nl ....
i=1
Therefore, it suffices show that 1 X TP, :., 2,
0 m3
0
( We first note that
nn
since 5 o(e). Therefore, Pr TP a, 7 bl = 0] 0(1) Pr Tp = a, T b|p =
Pr T =a, T9 x + (Pr IT T x-
by Claim A.2 suffices show that I = Σn
T T, b|x +Pr
TP T. x
'Note that closeness tester A should in principle receive two sets of samples (or two sample count vectors in the Poisson sampling model) simply concatenate the two sample count vectors together. we denote by (p @ q) the non non-negative measures over [2n].. where the first n entries agree with p and the last entries agree with q. Then the distribution over the concatenated sample count vectors is simply given by Poi(m, p c q).
from p and the other from q. However, it is not hard
that do not notational convenience,
lose any information
40

---

0 m 287) We next expand Pr IP a, a, b|x 0)
Pr T = a, 7 b|x = 0]
1
1
al (1 c)a exp( c)) bl
(1
c exp(p(111 (1-c))
n - m 1
(m(2c 60)
a
m(2c + ca)
1
m(2c co)
m(2r - co)
exp
exp
2n
al
2(n m)
2(n m)
bl
2(n m
2(n m)
n m
[m(2c + 60)
m(2c + (D)
m( (0)
m(2c - (o)
exp
2n
bl
2(n m)
2(n m)
a!
2(n m)
2(n m)
m
(1 - c)ath exp( 2(1 - <)) +
n m
m(2c + co)
m (2c - 60)
b
2mc
a.b!
2n
2(n m)
2(n m)
12 m
(2( + 6b)
m 2E - Eo)
2m
exp
=: fa,(Ee))
2n
2(n m)
2(n m
m
Then it follows that
i 0(1 Σ all! Sab((o) + Sa,((e)) a.bER.o
0(1)
Σ Ia.b
0,hE720
where we denote Ta,b abd faale))
faslee) To bound Ta,; we break into 3 cases regarding the
value of a.
when a + 0, viz. a a= b 0, Pr rp = 0, 0/ = = Pr = 0, 0| -|
m 2-p - +)) + n-m exp
2me nー
Therefore, To.o = 0.
when + b wlog 0, (by the symmetry between and b.) We have that
Pr
TP = T 1|X = 0| Pr
TP 0, 0, = 1|X =1
m
(1 - c) exp(-pppp -2(1 - -c)) +
m
mm(2 6o)
exp
2me
2n
2(n m)
m
- m
m(2e + 60)
2me
exp
2n
2(n m)
m
(1 c) exp( -2(1 ))) +
em
exp
2me
m
Thus. Io.1 In,0 0.
41

---

when a + b
>
1, wlog I b, then the denominator term fa,b(co) + fab(()) = = ( - c))tt)
On the other hand consider the numerator. When y E (1b
θ dy
fa,b(v)
n1
m
2m
exp
2n
m
m
m(2 + y)
a-1
(m(2 - 11)
m(2 + y)
)
a
[m(2e - 11) 6-1
-
2(n m)
2(n1 m)
2(nn m)
2(n m)
2(n m)
m
m22c + y)
b-1 mm(c - y)
(m(2c + y)
m(2c 11
+ 2(n m)
b
2(n m)
2(n1 m)
2(n m)
2(n2 m)
m
m
a+b-1
(2e + y) a-1 (2c - y) 6- [2e(a a b) - yla + +b)]
n 2(n m)
+ (2c + y) 6- (2c y) (26 (b- a) y(a + b)]
Let 1 be such that n m n2 then
c
a+b
[2e a) (2c + y) w- (2c - y)a=1 - -(2c + y) 0- (2c y)²
a--1g ty(a + b) (2c + 1)8 12e 11)a1 + (2c + y)²
a- -2e - y) -
S D(catb)
(m)
a+b
c(a + b) (2c +1) 3)) (2c - y) + (2c + y) n- (2c - y)"
=0 (4c)
m7 a+b
E <atb-l (a +
This implies that Va b2bb22 2, Ta.b =0
(4c)
a+b
2a-2h-1 2h-1 2(a+b-1)(e)) b)282
b))
then
alb!
1-c
Σ 0 a,bEZz0 a-hh?
Σ
(4c)2
a
(4c)2
b
m
2a+26-1
e
2(a+b-1)
(a
6)282
a=0
a!
1-e
biz 622-a
bl
1-e)
7
a5b
(4c)²) b
where Σ 82a t
I-c
<
exp((4c)²/(L +)) and the sum of infinite geometric series is domi-
622-a nated by the first term when common ratio < 1, we have that
Σ Ias= =0
0
Σ
1
(4c)²)
202 = =0(()) (mm) 202
Σ Topb e, a+b22
a!
a 0+622
a5.
02b
as desired.
In conclusion, from the above cases we have that
=0 (m)) 3
I I Io.0 + Io.1 + I1,0 + Σ
La, +
Σ
Lab=
282)
a,bEZzo a+bb2
a,bEZzo
a+b22 aSb
a2b
which concludes the proof of Lemma F.4.
Lemma F.5 (Lipchitzness of Expectation of Acceptance Probability Function). Assume that m
o(n2/3g 4/3 10pp-2/ 2/3 + n), and A be a deterministic tester takes a sample-coue count vector over in] as input and returns I if accept 0 otherwise, and recall the acceptance probability function is defined via
Accm (p, q, A)= == PPT--PuS(mpppq) (A(T) = Accepp) Let 6n < 61 E [0, c be such that 61 - 6g S cp.
Then it holds that
E (p.g)~A, [Acem (p. q, A)] - -,,, AAcm q.)]] < 0.1
42

---

Proof of Lemma F.5. Assume ((p.a))~,,, [Acc (p. q A)Jl 0.1. Then, let X be unbiased random bit, and Y be the random variable defined follows: let (p.q) Nex. T PoiS(m, t q), then Y if A(T) accept, Y ((p.a))N., [Acem (p,, q, q. A)] and Pr(Y 1|X 1] ()),N [Acc,, (p. q. A)], which implies mutual information bound of (X T) (X Y) (1() This contradicts with the result from Lemma F.4.
the opposite
((p.q)~-N,, [Acem (P. q.
otherwise. From the definition, we notice that PriY 1 = 0]
We now ready prove Lemma F.3.
Proof of Lemma F33. Since A is 0.1-correct w.r.t No and Nº. we have that ~ [Acem (P, A)] 2 0.9 and B(p.q)_N, (Acem (p, q. < 0.1. Furthermore, since - [Acem (P, A)] is polynomial in &, it is continuous in ç. then by mean value theorem there exists 5" E (0, such that E (p..))-Ng- [Acem (p. q. A)] 1/2. Immediately following from Lemma F.5 that vy E [5" pe, 5 + pe] we have that
((p.a)~Ng [Acem (p. A)] (E(p. [Acem (P. q A)] - 0.1, ( (p..)) [Ace, (p. q A)] + 0.1)
00.4,0.6) C 2133,2/3).
In conclusion, if we uniformly at randomly select a E [0,e]. then once it falls in interval 1s* pe, + pe] of length 2pe have that () (Accm (P, q A)) E 21/3,2/3) desired.
Conditioned on some & satisfying the probabilistic condition Lemma F.3, we then proceed to show that the acceptance probability Accm (P, q. concentrates around the expected acceptance probability ((p.a)~Ngg [Ace, (p, q..
F.2 Concentration of Acceptance Probabilities
In this section we prove that the acceptance probabilities concentrate.
Lemma F.6 (Concentration of Acceptance Probabilities). Let & E (0,s) and A be deterministic tester satisfying that is log" -2 rn-replicable with respect to Hc. Then it holds
( (p. q, A) - -Eip' [Acem (p''''''',.' A).
Pr (p.q)~-G
4 2
This is achieved by analyzing the sample random walk RW m.N; analogous to the one considered in the uniformity testing case.
We begin by defining a random walk on samples drawn from distributions in Ng..
Definition F.7. The Sample Random Walk RW m.g is defined on the graph with vertex set N2n (where each vertex corresponds to sample count vector T drawn from PoiS(m, p + q).) and transitions (Ti, T2) are defined by the conditional distribution T2 given T1 induced by the joint distribution given by the following process:
1. q) Nog
2. Ti, T2 are independently sampled from PoiS(m, @ q).
For any sample count vector T, let RW, m.g (T) be the random variable representing the next step of the random walk from T.
Given a sample count vector T, we denote T, Tp (resp. T (i))) the frequency of bucket from (resp. q). Let us analyze the random walk RW m.g. As before, we have Tp ~ Poi (mp,; and Ta [ ~ Poi (mq:) independently for all Thus, RW,, m.g is the product of independent random walks RW m.g.e on vertex set [m] x [m]. We describe RW m. by describing each random walk RW m.g
43

---

If S,T are drawn from the joint distribution defining RW m.g,b
Pr(Sppi] a, Tpl: = S.li - c, =d)
m. (((-e) =) =
71
a!blc!d!
/ e(2++5)m/(nnm)
(2++E)m atb 2(n
e(2e-E)m/(n-m) (n-m)
(26-E)
2n
a!b!
cld!
e (2r- (20-E)m/(n-ee (n-m)
(25-E)m a+b (n-m)
e(2cte)m/(n-m)
(26+E)m p mm)
+
a!b!
cld!
me (1-=)) (1 5) ()atbtetd
atbtotd gemm/(n-m)
n1
m.ablllld!
2n
2(n m)
abble!d!
where
fa+b.c+d(E) (2x + g)ath (2s -) E)
+ (2x -
1ytth(2e- (2s + E)
Similarly, we compute the marginal distribution as
Pr(Spp]] = Sqli] = c) me 21 55) (1 E)ato ato
22mm/(n-m)
12 - m
772
(e)
alc!
2n
2(n m)
alc!
To describe the random walk transition probability, compute the conditional distribution
P((a, (b, d)) = Pr(T, [1] = b, l = Sp = a, S =c Pr(T, = b, - a Sq
Pr(Spp( = a, Sqli =c)
and note that before, the stationary distribution is given by the probability vector <(a,c) Pr(Sppi] = a,
Following identical arguments as Lemma 3.9, we show that over few steps of the random walk, the outcome of the algorithm does not change significantly.
Lemma F88 Let AA be (100)) PoiS(m. p 4 q). For 1 < k < K, let Ts RW RWm. mTT(TT- Then.
with respect to He. Let (p.q) ~ Ng and To ~
(ULACTH1)+CCII
K
1
Pr To.... Th
<
10
We now bound the mixing time of the random walk RW m.g. As the argument for uniformity, we begin by bounding the (constant) mixing time of single coordinate.
Lemma F.9. Suppose m S n/10.. The random walk RW m.g,i has mixing time r(0.11) O(1).
Proof. Let Yo = (L1, f2) denote the current step. Let X ~ (A, be drawn randomly with probabilities
m n 2n
n- m
n-m respectively. Let 2 Poi (1 - 2) Poi 2n
(2s+C)m
z ~
2[n-m)
Poi (2c-E)m² and Z ~ Poi (1 x), 7 Poi (2 2(x-m)
7 ~ Poi (2c+
The next
2(n-m)
2(n-m)
step of the random walk Y1 ~ RW (Yo) is taken according to the distribution
P((e1,8)) (k) k2)) = Pr(x = A Yo = (4. = ki, U3 = k2)
+ +P((X = B Yo = (41,4) Pr(ze = =kı = k2)
+ PPr(X C Yo
= =k,, k, = =k2).
44

---

We show that regardless of the current state (41, f2), the random walk reaches state (0, with reasonable probability. Since 0.1,
Pr(z7 = 0, Σ = 0) = e (1--)) (1
-===0) 2
2 20.13, c
-2(-E))
0!
=
Pr(Z) = 0, 22 0) =
2(n wyy
(2m+ (2e-5)m
e
2(n
mJ
25 > 0.8, 2 c 1
2em
Pr(Zf 0, 0g 0) 0.8
where we have used m < nn/10 in the second bound. In particular, note that S (here we only use that 1/9 1). The last follows identically. Then, regardless of (L,, f2), we have P(((),))) (0, 0)) 2 0.13. In particular, after O(1) steps, we can guarantee that with probability 0.99 we reach the state (0,0), 0). We can then assume without loss of generality that & lz = 0.
We now examine the distribution of X conditioned on Yo- 0), First, note that
Pr(Yo = (0)
-((1-))
+ 2n
2cm 2/mm(nn-mu) (m) e- ---ee//(n (n)) m)) EE
71
m 2(1-5) +
n m
2em/ (n-)nn-m)
Then, we argue that distribution of X conditioned on Yo = (0, 0) is reasonably random.
Pr(X = B Yo= = (0, = Pr(X = B, Yo (0.0))
Pr(Y, (0
22/(n-m)
e 2 =) + n-m E 22 m))
1/2
2em
2(1 - E)) +
cxp
n-m
n-
Observe
m < m2 exp
(-2) S exp
2am
2(1 - -)
S
2m n
exp ( -1.8 -
m
so that
I0m
7--1
applying 0.5
0.5
< 0.5
x/3 for small
0,
1
0.5 - m
< Pr(X = B Yo (0.0) 0.5 m
n
30n'
As a result, we can conclude
2m
S Pr = A A Y (0,0)) <
15n
n
In the stationary distribution, we have
Pr(X = A) m
Pr(X = B) = CC n1 m
2n
In particular, the total variation distance between X in the stationary distribution and X conditioned on Yú = (0, 0) is at most @ S 1 using our assumption m S n/10. Thus, from initial state (0, 0). the random walk mixes within 0.1 total variation distance to the stationary distribution. We union bound with the 0.01 probability of not reaching the stationary distribution in O(1) steps to conclude the argument.
To
Thus, we can bound the relaxation time of RW m.g.i as
70011))
Crol
+1=
(og(1/0.22)
We now bound the mixing time from the initial distribution.
Lemma F.10. Let m S n/ n010. Let (xx) ~ Poi (1 E) & Poi -)) s), 7xx) ~ Poi
(25+E)m Jm
2(n-m)
Poi (2e-E)m 2(x-m) or 7(x) Poi
(2m 2[n-m)
Poi (2c+5)m 2(n-m)
denote the initial distribution. The
random walk RW m.g.s has mixing time ( Olog((n6)).
45

---

Proof. As in Lemma E.8, we begin with following the inequality for any pair of states 2 = (2) and y (111 32).
(1.))"(()0)-)000))) Xx(x))((1)
(T(x)
We bound the ratio (x))/T(z)) Claim F.11. For all states x (2),
{x) T (2x)
S
Proof. We split into the cases
ZA 7 7.8 . 70 as defined in Lemma F.9. First, we write
T(x)=
m
Pr(z
=
n1 1- m
Pr(z = + n2 - m
Pr(z x)
2n
2n
Then
Pr(ZA = x)
Pr(ZA x)
91
((x)
m
Pr(Z 1 = x)
m
a
Pr(Z B = x)
Pr(Z = x)
2n
<
<
(2)
Pr(ZB x)
2n
Pr c x)
5
क (x)
where in the second and third cases we used n/2. Finally, conclude by observing
n 2 4.
Then, we sum over to observe
[ (()) x(v)
S.y. =T()) Σ V7(1). m
We now bound Σn (x() In all three cases Z4, 7B, n0, we have that the Poisson distribution (in both distributions) has parameter X < 1. By standard Poisson concentration, for any E {1,2] and D E (A have
Pr(Z? x) Pr(Z,- X A 1)) 1)x-1)
Then, we bound for any X E [A,
Σv1()== = Σ Σ
V Pr (2F = =1) Pr (2,- x2)
#1=0 =y=0
Σ
Pr(22 =x1)
Σ F2=0
Prx = x1)
=1=0
0(1).
where the first equality follows by definition of 7 and independence of p. q. and the second and third equalities follow as Σn /Pr(Z, = 2) converges absolutely, which we showed Lemma E.8.
Thus, we arrive at the inequality
Σ (x)0))((.))) T(v) = (AL (xE m
(())
Summing over y and applying a similar argument (see Lemma E.8 for details), we obtain
Σ
Σ (xx)
TTV) 0 2
72
m
46

---

Thus, since A2 < 1 is an absolute constant less than 1, we conclude that from any of the three initial distributions, the random walk RW m.g.i mixes within å of the stationary distribution in time T(6) 0(l) Ollo((n()).
Now, using identical arguments as in Lemma E.10, we can conclude with the following lemma. Lemma F.12. Let K = -(0.01) and ç E [0, Suppose A is 1
10k -replicable with respect to Hc-
Then,
Pr (p.g)oWV
(BT~(P-) [A(T)] p [A(T']] >
S
We now prove Lemma F.6.
Proof. From Lemma F.10, we have that 70001 Ollo n)). Since A is log n-repicaaalee w.r.t. He, it also 1/(10a)-replicable w.r.t. Hc. The conclusion follows.
F.3 Proof of Proposition F.2 and Theorem 1.4
Combining Lemma F.3 and Lemma F.6 then yields the proof of Proposition F.2.
Proof of Proposition F2. The proof follows using analogous arguments as Proposition 3.4, applying Lemma F.3 and Lemma F.6 where appropriate.
We are ready to prove Theorem 1.4. The theorem follows from Proposition F.2 and Lemma D.3.
Proof of Theorem 1.4. Note that a lower bound of ( + + --ーー) follows immediately from lower bounds for uniformity testing and bias estimation respectively. It suffices show lower bound of g 1/3 -2/3/32333///)) 2/33).
Proposition F.2 says that any deterministic tester that is 0.01-correct takes Poissonized samples with sample complexity m g/ -2/33 is not p/ (log rr)-rreplccabee with respect the hard instance Hc. Then, from Lemma D.3 we may conclude that any randomized tester with fixed sample complexity m 2/32 4/3 2/3) is not reeellcaabl with respect to Ho, concluding the proof.
47


Reviews:
[{"review_id": "cChUObxJfK", "reviewer": "Reviewer_E3L9", "summary": "Given sample access to a distribution, property testing is the problem of determining if the distribution has property $P$ or is far from any distribution with probability $P$. An algorithm is replicable if repeated runs of the algorithm give the same answer whp. In this case, that corresonds to consistently classifying a particular distribution the same way whp, regardless of the exact set of samples you get for the distribution. The paper gives upper and lower bounds for replicable property-testing algorithms for a couple of key properties, including tight bounds for closeness testing and n-item uniformity testing.", "questions": "There's an indirectly related proof of lower bounds for replicability in https://arxiv.org/pdf/2304.03757, https://arxiv.org/pdf/2503.15294 and https://arxiv.org/pdf/2304.02240v1 Both show roughly that you can't replicably distinguish between things if things more or less continuously change into each other. There's a follow-up with sample complexity stuff here https://openreview.net/pdf?id=2lL7s5ESTj.\nThose papers required that there is a set $S$ of size $k$ s.t. $A[samples, randomness]\\inS$ whp, which is slightly different but related to the constraint that $A[sample1, randomness] = A[sample2,same randomness]$ whp. But I think it could simplify your lower bound proofs.\n\nFrom what I can tell, your main technical contribution is the random walk analysis to establish the space of similar distributions. Is that fair to say?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "+ Tight sample complexity bounds for replicability for some fundamental problems\n+ Neat random walk argument to establish that on similar distributions the tester will behave similarly\n\n? I did not verify the proofs, which are extremely long and technical", "was_revised": true, "final_justification": "I still think that the sample complexity bounds are interesting because they are on fundamental problems for replicability. The random walk argument continues to be neat. I still have not verified the proofs, which are still extremely long and technical\n\nThe authors and other reviewers have convinced me that the paper is more original than I thought. Therefore I have updated my Originality score.", "rebuttal": "Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.\n\nMostly an improvement of existing arguments and algorithms using known techniques\n\nWhile the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.\n\n“can’t distinguish things… continuously change”\n\nWhile our lower bound relies on the general framework that similar distributions cannot be distinguished (also observed e.g. for mean estimation [33, 34]), the hard instances for distribution testing consist of similar families of distributions (\\mathcal{M}_{\\xi} in the text) instead of single distributions. A barrier from previous work (which we resolve) is to show that the algorithm behaves similarly among all distributions in a particular family.\n\nConnections to List Replicability (Randomness and Sample Complexity)\n\nFinally, list replicability does not seem to have any immediate implications for distribution testing as there is a 0-sample algorithm that is replicable with list size 2 (output both {0, 1})."}, {"review_id": "XarxJEU6IV", "reviewer": "Reviewer_hQvc", "summary": "The paper studies the problem of distribution testing with replicability constraints. Given samples from k distributions, the distribution testing problem aims, in general, aims to design a \"replicable\" tester (algorithm) that distinguishes between the cases when all k distributions satisfy a certain property or if one of them is far from the property. This work in particular focuses on uniformity testing, closeness testing, and independence testing problems. These distribution testing problems without the replicability constraint has been well studied. The main results show tight tradeoffs in sample complexity with this added constraint.", "questions": "Please see the previous section for connections to tolerant testing and private testing.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The results are a good addition to the literature on distribution testing, and the techniques while similar to ref 27 (in the manuscript) require certain delicate balancing and are quite novel. The paper overall is quite well-written. The main technical differences from [27] while adequately addressed is a bit confusing at first without reading the definitions that follow in later sections. In my personal opinion, a slight rephrasing could help, but is not a major concern. Hence i would recommend accepting. \n\nConnection to Tolerant Testing: It is however unclear why a tolerant tester that distinguishes between $\\xi(\\rho)$, and $\\epsilon-\\xi(\\rho)$ for independence testing is not sufficient. At a high level, it seems intuitive that two independent sets of samples from the same distribution will be close, and hence from triangle inequality, should ensure that two induced distribution be either close or far from the property.  \n\nConnection to Private Testing: Another connection that has been leveraged, but not discussed is the connection to differentially private testing. This stems from the intuition that modifying even a single sample should not change the tester's output with high probability. Will the lower bounds of differentially private independence testing carry over to this setting?", "was_revised": true, "final_justification": "I am convinced by the author responses, and recommend accepting the paper.", "rebuttal": "Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.\n\n“similar to [27]” \n\nWhile the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.\n\nConnections to Tolerant Testing\n \nWhile tolerant testers do imply replicable testers, our algorithms are significantly more sample efficient than any tester obtained in this way (see also discussion in [27]). For example, a natural approach to a replicable test is the following: sample a random threshold r between 0 and eps, and run a tolerant tester with thresholds r - \\rho \\eps, r + \\rho \\eps. Even for constant tolerance, the sample complexity is barely sub-linear in the domain size n. Thus, even for constant \\rho, and \\eps the sample complexity of a replicable tester will be barely sublinear in n. In contrast, all our algorithms have strongly sub-linear dependency on the domain size parameter.\n\nConnections to Private Testing\n\nWhile m-sample private testers give rise to m^2-sample replicable testers [12] the sample complexity is suboptimal by a polynomial factor (as discussed in line 52), and in fact linear in n. We do mention that our algorithm for independence testing is inspired by the randomized flattening technique that has been leveraged for designing private independence testing algorithms (see line 173).\n\nOn the lower bound side, while private testing lower bounds imply replicable testing lower bounds [12], they will not give any non-trivial lower bounds (beyond standard lower bounds for uniformity testing). This is due to the fact that the known equivalence [12] will only give lower bounds for constant replicability \\rho. (In particular, they show a constant replicability algorithm already implies a private algorithm).\n\nAlthough the current connection is not strong enough to obtain sample-optimal bounds, the connection between replicable and differentially private testing remains an interesting one, and it is possible that a stronger quantitative relationship than what was proven in [12] would allow us to obtain tight bounds."}, {"review_id": "0Kr9oJWkvW", "reviewer": "Reviewer_4xTX", "summary": "This paper studies replicable property testing of discrete distributions, under the shared-randomness replicability definition proposed by Impagliazzo et al. Recent work of Liu and Ye studied the specific problem of replicable uniformity testing. This paper strengthens and generalizes their results in several dimensions. First, it introduces a framework for proving replicable distribution testing lower bounds, which gives nearly tight results for both uniformity and closeness testing. The framework takes the same conceptual approach as Liu and Ye, who were able to prove lower bounds for symmetric testers, but bypasses the need for this assumption by identifying and studying a particular random walk to show that an arbitrary tester behaves as though it were symmetric in the right way.\n\nSecond, it designs new replicable testers for closeness and independence testing. Building again on the work of Liu and Ye, it argues more generally that testers which involve thresholding a test statistic can be made replicable by randomizing the threshold. Getting this to work for independence testing involves some additional ideas for stabilizing the test statistic, which were originally introduced for differential privacy.", "questions": "* Does the lower bound framework give anything nontrivial for replicable independence testing?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(+) Distribution testing offers an important and well-studied class of problems as fodder for identifying optimal replicable algorithms.\n\n(+) We're still lacking strong / general-purpose techniques for proving replicability lower bounds, so the framework this paper offers (in particular, showing that the approach suggested by Liu and Ye does not require as strong assumptions about the structure of the learner as previously thought) is quite welcome.\n\n(+) Both the positive and negative results identify broadly applicable principles for replicable distribution testing and algorithmic replicability more generally.\n\n(+) The writing is clear and appears sound (though I did not check details carefully).\n\n(-) The paper's novelty lies in its technical contributions (which are nice), but it doesn't offer much that is new conceptually.", "was_revised": true, "final_justification": "This submission makes a solid technical contribution, and discussion with the authors did not raise anything to significantly change that impression.", "rebuttal": "Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument. In what follows we will address the concerns of the reviewer regarding the significance of our conceptual contribution and questions regarding related proofs.\n\n“doesn’t offer much new conceptually”\n\nWhile the closeness testing algorithm follows the general paradigm in replicable algorithm design of comparing a randomized threshold to a strongly concentrated test statistic, our independence tester is significantly more involved as known test statistics do not satisfy the required concentration bounds. Furthermore, our main technical contribution is the first unconditional lower bounds for replicable distribution testing (removing the previous work’s assumption that the given algorithm is symmetric and proving a new new-optimal lower bound for closeness testing). Our random walk argument to show that any algorithm’s output under a given family of distributions is well concentrated is novel in this context, specifically does not appear in prior work within this field.\n\n“lower bound framework … replicable independence testing”\n\nWe believe that our lower bound framework likely yields non-trivial (and quite possibly optimal) lower bounds for independence testing. However, the hard instance for independence testing is much more complicated than those for uniformity and closeness. Thus, the computation of mutual information (to show similar families cannot be distinguished) and the analysis of the eigenvalues of the random walk (to show that the algorithm output is well concentrated within any given family) would be significantly more challenging. We believe that this is certainly an interesting direction for future research."}, {"review_id": "0waWonG3Zh", "reviewer": "Reviewer_6dkn", "summary": "The focus is on replicable testing (uniformity, closeness, etc); that is we are interested in testing algorithms that with high probability output the same thing on two different independent draws (using the same randomness). \n\nThe main result of the paper is thm 1.3, setling down (up to polylog factors) the sample complexity of replicable uniformity testing, showing that the existing algorihm is in fact nearly optimal. As an aditional application of the developed techniques (which to some extent mimic the previous work up to a new random-walk argument), the authors provide lower bound on the sample complexity of closeness testing and give a (linear time) algorithm matching this lower bound up to polylog factor. The final interesting point of the paper I want to discuss here is the observation that replicable testing has suspiciously similar complexities with high probability testing and I like that it is emphasized as an open question.", "questions": "-", "limitations": "-", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper is very dense and was not that easy to read, but this is to be expected as it is very technical and I do not have suggestions in this regard. The studied problem/field is rather new and is somewhat niche, but I believe the replicability is an important property of testers and should be understood. To this end, It is likely that this paper will become a canonical reference.\n\nOverall, I consider the presented results in the paper to be very strong and (unless there is an error that I missed, **I haven't checked technical details**) should be clearly accepted. \n\n\ntypos in alg 1, line \"2: \".", "was_revised": true, "final_justification": "-", "rebuttal": "Thanks for the detailed response. We are encouraged by the positive comments about our tight sample complexity bounds for fundamental problems and the novelty of the random walk argument."}]

Author rebuttal:

Meta-review: This manuscript applies replicability in learning introduced by Impagliazzo et al @ SOTC'22 to testing properties of distributions and  answers the open question related to replicable uniformity testing posed in Liu & Ye @ NeurIPS'24. While the proofs in this work are quite long and technical [E3L9] and there are no conceptual novelties [4xTX], the work is considered a good addition to the literature on distribution testing [hQvc, 4xTX] as it clarifies technical differences from prior work [hQvc] and offers technical novelties [4xTX] and results are perceived as both relevant and elegant [E3L9].
Decision: Accept (spotlight)