Replicable Distribution Testing

Christopher Ye; Daniel Kane; Ilias Diakonikolas; Jingyi Gao; Sihan Liu

REVIEW 3 major objections 4 minor 47 references

Replicable Distribution Testing

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper settles the sample complexity of replicable uniformity testing up to logarithmic factors, and gives near-matching bounds for closeness and independence testing.

desk verdict A genuinely new lower-bound technique that likely settles the open uniformity testing question, with a few repairable gaps in the random-walk concentration proof. read the letter →

arxiv 2507.02814 v1 pith:462ETXV5 submitted 2025-07-03 cs.LG

Ilias Diakonikolas , Jingyi Gao , Daniel Kane , Sihan Liu , Christopher Ye This is my paper · ORCID

classification cs.LG MSC 68W2062G1060J10

keywords algorithmicreplicabilitydistributiontestingsamplecomplexityuniformityclosenessindependencerandomwalkmixingPoissonization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that any algorithm which (ε,ρ)-replicably tests uniformity over a domain of size n must use $\widetilde{\Theta}(\sqrt{n}\,\varepsilon^{-2}\rho^{-1}+\varepsilon^{-2}\rho^{-2})$ samples. This settles the open question left by the earlier replicable uniformity tester, and it does so without assuming the tester is symmetric. The same lower-bound technique gives a matching bound for closeness testing, and the paper supplies new replicable testers for closeness and independence whose sample counts match the bounds up to logarithmic factors. The result matters because replicability—returning the same answer on two independent sample sets—is a formal stability guarantee, and knowing its exact sample price lets practitioners compare replicable testers with standard high-probability testers.

What carries the argument

The central machinery is the sample random walk $\mathrm{RW}_{m,\xi}$ on the space of sample-count vectors: pick a hard distribution from the meta-distribution, draw two independent Poissonized samples, and let the walk transition from one count vector to the next. Because Poissonization makes coordinates independent, the walk factors into n scalar random walks; the paper proves these scalar walks have constant relaxation time and hence O(log n) mixing time, which is exactly what lets the lower bound avoid any symmetry assumption on the tester. On the upper-bound side, the key devices are comparison against a random threshold and an averaged version of an existing independence statistic, whose variance is controlled by an Efron–Stein argument through the expected number of non-singleton flattened samples.

What would settle it

Run the coordinate random walk of Lemma 5.13 for a concrete large-epsilon setting, for instance ε=0.2 and m close to n/ε², and measure the total-variation distance from stationarity after two steps from a range of starting counts; if any starting state stays more than 0.04 away, the claimed mixing time is false. Also, the stated deduction 0.4ξ < 0.04 already fails for ξ=0.2, so a direct numerical check of the two-step distribution, rather than the proof's inequality, is what would settle the claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that the sample complexity of (ε,ρ)-replicable uniformity testing over [n] is $\widetilde{\Theta}(\sqrt{n}\,\varepsilon^{-2}\rho^{-1}+\varepsilon^{-2}\rho^{-2})$. The lower bound is proved by constructing a meta-distribution over hard instances and showing, without any symmetry assumption on the tester, that acceptance probabilities concentrate around their average when the tester is moderately replicable. The key vehicle is a random walk on Poissonized sample-count vectors that mixes in O(log n) steps, letting the authors transfer an average acceptance probability to individual hard instances. With upper bounds from a random-threshold closeness tester and an averaged independence statistic, the paper also gives near-tight sample complexities for replicable closeness testing and the first replicable independence tester.

Load-bearing premise

The load-bearing premise is that the sample random walk mixes in O(log n) steps under the paper's parameter ranges; if that mixing is actually slow, the concentration argument that carries average acceptance probabilities to individual hard instances fails and the lower bound collapses.

Editorial extensions

If this is right

The earlier replicable uniformity tester is sample-optimal up to logarithmic factors, so no future algorithm can beat the $\widetilde{\Theta}(\sqrt{n}\,\varepsilon^{-2}\rho^{-1}+\varepsilon^{-2}\rho^{-2})$ barrier.
Replicable closeness testing has sample complexity $\widetilde{\Theta}(n^{2/3}\varepsilon^{-4/3}\rho^{-2/3}+\sqrt{n}\,\varepsilon^{-2}\rho^{-1}+\varepsilon^{-2}\rho^{-2})$.
Replicable independence testing over $[n_1]\times[n_2]$ can be solved with $\widetilde{O}(n_1^{2/3}n_2^{1/3}\rho^{-2/3}\varepsilon^{-4/3}+\sqrt{n_1n_2}\,\rho^{-1}\varepsilon^{-2}+\rho^{-2}\varepsilon^{-2})$ samples.
The new lower-bound framework applies to replicable distribution testing generally, so future lower bounds can be obtained without imposing symmetry on the tester.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the mixing-time lemma survives scrutiny, the same sample-walk argument should yield matching lower bounds for replicable identity testing and independence testing, which the paper leaves open.
The formal resemblance to high-probability testing suggests the hypothesis that replicable testing is equivalent to high-probability testing with failure probability set to ρ, up to logarithmic factors; a generic reduction in either direction would unify the two lines of work.
The averaging procedure used for the independence statistic may be a general recipe: any statistic that is Lipschitz under deleting singleton samples can be stabilized by averaging over internal randomness, which could help convert other high-probability testers into replicable ones.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main event is the lower-bound framework in Section 5. The random-walk construction lets the authors prove concentration of acceptance probabilities without assuming tester symmetry, which is exactly what was blocking the field. That is a real step forward, and it appears to deliver the first unconditional near-optimal lower bound for replicable uniformity testing, plus a tight closeness bound. The upper bounds for closeness and independence are clean adaptations of known high-probability testers, and the connection to the high-probability regime is worth stating explicitly.

The soft spots are real but, I think, repairable. The stress-test concern about Lemma 5.7/5.17 is legitimate: the proof uses global replicability with respect to HU to draw a pointwise conclusion for a fixed ξ. The text does not handle ξ where κ(ξ) is large. The saving grace is that for those ξ the desired non-replicability statement already holds, so a case split in Proposition 5.5 would fix the argument. But as written, the concentration transfer is not established. This is the load-bearing point of the lower bound, so it must be patched.

There are smaller issues. Footnote 6 admits that removing the log^{-2} n replicability requirement needs an eigenvalue argument that is deferred. Lemma 5.13 has a constant error: 0.4ξ < 0.04 is false for ξ close to ε when ε > 0.1. The asymptotic mixing time survives, but the line is wrong. Lemma 4.10's "almost identical" case analyses in the independence tester are sketched rather than shown; they deserve fuller proofs. The imports from [DGK+21] are fine - they are published results with independent proofs, and the present results do not appear to assume what they are proving.

Overall, the paper is significant and the framework is likely to be reused. It deserves a serious referee. My recommendation is to send it to peer review, but with the clear instruction that the authors must address the pointwise-versus-average gap in Lemma 5.17 and fix the small errors before it is accepted. The central claims are probably correct, but the proof as written is not fully verified.

Referee Report

3 major / 4 minor

Summary. The paper studies distribution testing under algorithmic replicability. It states three main results: (1) a near-optimal sample-complexity characterization of replicable uniformity testing, Theta-tilde(sqrt(n) epsilon^{-2} rho^{-1} + epsilon^{-2} rho^{-2}); (2) a tight lower bound for replicable closeness testing; and (3) new replicable algorithms for closeness and independence testing. The lower-bound framework replaces the symmetry assumption of Liu and Ye with a concentration argument based on a random walk on sample count vectors, whose mixing time is claimed to be polylogarithmic. The upper bounds combine random-threshold testing with variance reduction, including an averaged statistic for independence testing. The proof is structured into Section 5 for lower bounds and Sections 3--4 for upper bounds, with deferred technical lemmas in appendices.

Significance. If the main claims are correct, the paper settles the open problem posed by Liu and Ye on the optimality of replicable uniformity testing and introduces a random-walk-based technique for proving unconditional lower bounds in replicable distribution testing, which appears genuinely novel. The upper-bound side is also significant: the closeness tester nearly matches the lower bound, and the independence tester demonstrates an averaging technique that may be reusable in other replicable estimation tasks. The paper is carefully written and the proofs are detailed, with explicit deferred appendices. However, the lower-bound argument as written has several load-bearing gaps: a pointwise-versus-global replicability issue in the concentration transfer, an incorrect constant in the coordinate mixing-time proof for part of the parameter range, and a mismatch between the distributional lower bound that is actually proved and the worst-case replicability lower bound claimed in Theorem 1.3. These issues are substantial but appear potentially fixable.

major comments (3)

[Section 5.2, Lemma 5.17 and Lemma 5.7] The hypothesis of Lemma 5.17 is that A is 1/(10K)-replicable with respect to the mixture HU, which bounds E_{xi~U[0,eps]} kappa(xi) <= 1/(10K), where kappa(xi) = Pr_{p~Mxi,T,T'}[A(T) != A(T')]. The proof then invokes Lemma 5.9, whose parameter kappa is precisely this fixed-xi quantity. A global bound on E_xi kappa(xi) does not imply the pointwise bound kappa(xi) <= 1/(10K) needed for the random-walk path stability argument. Since xi is continuous, kappa could be large on a small-measure set of xi without violating the global bound, and the proof of Lemma 5.17 contains no case split for such xi. Consequently Lemma 5.7, which asserts concentration for every xi under only global replicability, is not established as written. This step is load-bearing: Lemma 5.7 is used in Proposition 5.5 to derive equation (14), and the same pattern is repeated for closeness testing in Lemma 5.27. A correct proof needs either a pointwise replicability hypothesis or a separate treatment of the large-kappa region.
[Section 5.2, Lemma 5.13] The proof of Lemma 5.13 contains the assertions `2xi < 0.2` and `0.4xi < 0.04` in the sublinear case. Since the hard-instance parameter xi ranges over [0, eps] with eps allowed up to 1/4, these inequalities are false for xi > 0.1. The claimed two-step mixing time tau(0.04) <= 2 for the coordinate random walk is therefore not proven in the stated parameter range. This affects Theorem 5.10, Lemma 5.15, Lemma 5.17, and ultimately the lower bound for uniformity testing. The constants can likely be repaired by allowing the mixing parameter to be a larger constant (the argument would still yield a constant relaxation time), or by splitting the parameter range, but as written the proof is invalid for eps > 0.1.
[Section 5.2, proof of Theorem 1.3] Proposition 5.5 establishes only that a correct deterministic Poissonized tester cannot be rho log^{-2} n-replicable with respect to the meta-distribution HU. This is a distributional replicability statement at the much smaller parameter rho log^{-2} n, and it does not imply failure of worst-case (epsilon, rho)-replicability as defined in Definition 1.1: a tester whose disagreement probability is, say, rho/2 on every distribution would satisfy the proposition's conclusion yet still be rho-replicable. To derive the lower bound on the sample complexity of (epsilon, rho)-replicable uniformity testing, the proof must include an explicit replicability amplification step (e.g., running the original tester multiple times with fresh samples and taking a majority, at the cost of an O(log(1/rho)) factor in sample complexity) or otherwise bridge the gap between rho log^{-2} n and rho. No such argument appears in the proof of Theorem 1.3, so the stated Theta-tilde lower bound does not follow from the presented analysis. The final step of Proposition 5.5, which asserts Pr_{p~HU}[disagreement >= Omega(rho log^{-2} n)] >= rho from a rho-fraction of xi with E_{p~Mxi}[disagreement] >= log^{-2} n, is also not justified by the preceding Markov argument and needs clarification.

minor comments (4)

[Section 5.2, footnote 6] Footnote 6 states that fully removing the log^{-2} n replicability requirement requires an eigenvalue argument deferred to a future version. This admission is directly related to major comment 3, and the paper should either prove the stronger statement or explicitly state which version of the theorem is conditional on that future argument.
[Section 4, Algorithm 3 lines 3 and 7] The algorithm asks to estimate the expectations Na and Za up to o(1) error by running IndependenceStats with fresh randomness; the number of repetitions needed and the resulting effect on the sample complexity are not specified. The subsequent proof refers to a 'standard median trick' but does not detail how the median interacts with the variance bounds (e.g., Corollaries 4.11--4.13) or with the replicability guarantee.
[Section 2.3, Lemma 2.8] The proof of Lemma 2.8 is a one-line triangle-inequality argument that does not explicitly handle the maximum over starting states in the definition of mixing time. This is a standard fact, but the proof as written is too terse to be fully verifiable.
[Section 5.2, first paragraph] The sentence 'we assume that tilde-o(sqrt(n) epsilon^{-2} rho^{-1}) = epsilon^{-2} rho^{-2}' is unclear and should be rewritten; the comparison between the two lower-bound terms needs a precise statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; central derivation is self-contained, with a flagged non-circular proof gap in the lower-bound transfer.

full rationale

The paper's upper bounds import expectation-gap and non-singleton-count lemmas (Lemma 3.1, Lemma 4.6, Lemma 4.12) from the published STOC paper [DGK+21], in which two of the present authors are coauthors; these are external, parameter-free results with independent proofs and their assumptions do not include the target replicability claims, so the citations are real evidence rather than circular load-bearing. The replicable closeness/independence algorithms use the random-threshold strategy from [LY24] and a variance/Efron-Stein analysis performed in this paper; the lower bounds are derived from first principles via mutual-information bounds (Appendix B/C) and a sample-random-walk mixing argument. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. The only flagged issue is a correctness gap, not a circularity: in the proof of Lemma 5.17, the argument passes from the global (average-over-xi) HU-replicability assumption to a per-xi path-agreement statement, and the inference 'From Lemma 5.9 we know that on average over p~Mxi, A(T0) = A(T1) = . . . = A(TK) with probability at least 0.9' requires a pointwise kappa(xi) bound that the HU definition does not supply; this is load-bearing for Lemma 5.7 and Proposition 5.5, and the paper's own footnote promises a future eigenvalue argument to remove the log^{-2} n-replicability requirement. Because this is an unjustified logical transfer rather than an equivalence-by-construction or a fitted-input-as-prediction, it does not make the derivation circular; the appropriate place for that concern is correctness/rigor, not the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The results are purely mathematical; there are no fitted parameters or invented entities. The key external ingredients are standard probability inequalities and mixing-time theorems, plus the use of Poissonization to simplify lower bounds. The independence tester also relies on lemmas from [DGK+21] about the flattening procedure; these are cited as external results.

assumptions (5)

standard math Poisson concentration bound (Lemma 2.1)
Used throughout the Poissonized lower bound proofs, e.g., Section 5.1 and Appendix B, to control the sample count around its mean.
standard math Efron-Stein inequality (Lemma 3.3)
Used to bound variance of the closeness test statistic Z in Lemma 3.2.
standard math Markov chain mixing time bounds (Theorem 2.11 from [LPW06])
Used to relate relaxation time to mixing time in the lower bound framework, Sections 2.3 and 5.2.
domain assumption Poissonization is equivalent up to polylog factors (Lemma 5.3)
The lower bounds are proved in the Poisson sampling model and then transferred to fixed-sample testers; requires the measure norm condition ||p||_1 in (0.5,2), as assumed in Definition 5.2.
domain assumption Regime assumptions m = o(n/epsilon^2) (uniformity) and m <= n/10 (closeness) are valid for the claimed lower bounds
These are used in Lemmas 5.13, 5.15, 5.24, 5.25 to establish fast mixing; the omitted regimes are covered by other terms in the lower bound statements.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Replicable Distribution Testing." pith.science (2026). https://pith.science/paper/462ETXV5

@misc{pith2026250702814,
  author       = {Pith},
  title        = {Pith review of: Replicable Distribution Testing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/462ETXV5}},
  note         = {Machine review of arXiv:2507.02814}
}

read the original 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 46 canonical work pages

[1]

Acharya, H

J. Acharya, H. Das, A. Jafarpour, A. Orlitsky, and S. Pan. Competitive closeness testing. Journal of Machine Learning Research - Proceedings Track , 19:47--68, 2011

work page 2011
[2]

Acharya, C

J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems , 28, 2015

work page 2015
[3]

Aliakbarpour, I

M. Aliakbarpour, I. Diakonikolas, D. Kane, and R. Rubinfeld. Private testing of distributions via sample permutations. Advances in Neural Information Processing Systems , 32, 2019

work page 2019
[4]

Aliakbarpour, I

M. Aliakbarpour, I. Diakonikolas, and R. Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In International Conference on Machine Learning , pages 169--178. PMLR, 2018

work page 2018
[5]

Acharya, Z

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

work page 2018
[6]

T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating entropy. In ACM Symposium on Theory of Computing , pages 678--687, 2002

work page 2002
[7]

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. IEEE, 2001

work page 2001
[8]

T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In 41st Annual Symposium on Foundations of Computer Science , 2000

work page 2000

Show all 47 references

[9]

T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing closeness of discrete distributions. Journal of the ACM (JACM) , 60(1):1--25, 2013

2013
[10]

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 on Theory of Computing , pages 520--...

2023
[11]

T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In ACM Symposium on Theory of Computing , pages 381--390, 2004

2004
[12]

C. Canonne. A short note on poisson tail bounds, 2019

2019
[13]

C. L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing , pages 1--100, 2020

2020
[14]

C. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory , 19(6):1032--1198, 2022

2022
[15]

Chase, B

Z. Chase, B. Chornomaz, S. Moran, and A. Yehudayoff. Local B orsuk- U lam, S tability, and R eplicability. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, 2024 , pages 1769--1780. ACM , 2024

2024
[16]

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

2017
[17]

C. L. Canonne, I. Diakonikolas, D. M. Kane, and S. Liu. Near-optimal bounds for testing histogram distributions. CoRR , abs/2207.06596, 2022. Conference version in NeurIPS'22

2022 arXiv
[18]

C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing B ayesian networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017 , pages 370--448, 2017

2017
[19]

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, 2018 , pages 735--748. ACM , 2018

2018
[20]

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 on Discrete algorithms , pages 1193--1203. SIAM, 2014

2014
[21]

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 , 2022

2022
[22]

Daskalakis, N

C. Daskalakis, N. Dikkala, and G. Kamath. Testing ising models. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, 2018 , pages 1989--2007. SIAM , 2018

2018
[23]

Diakonikolas, T

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

2021
[24]

Diakonikolas, T

I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Sample-optimal identity testing with high probability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , pages 41--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2018

2018
[25]

Diakonikolas and D

I. 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

2016
[26]

Diakonikolas, D

I. Diakonikolas, D. M. Kane, and S. Liu. Testing closeness of multivariate distributions via R amsey theory. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, 2024 , pages 340--347. ACM , 2024

2024
[27]

Diakonikolas, D

I. 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

2015
[28]

Diakonikolas, D

I. Diakonikolas, D. M. Kane, and V. Nikishkin. Testing identity of structured distributions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , pages 1841--1854. SIAM , 2015

2015
[29]

Diakonikolas, D

I. Diakonikolas, D. M. Kane, and V. Nikishkin. Near-optimal closeness testing of discrete histogram distributions. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , volume 80 of LIPIcs , pages 8:1--8:15. Schloss Dagstuhl - Leibniz-Zentrum f...

2017
[30]

Eaton, M

E. Eaton, M. Hussing, M. Kearns, and J. Sorrell. Replicable reinforcement learning. Advances in Neural Information Processing Systems , 36, 2023

2023
[31]

Esfandiari, A

H. Esfandiari, A. Kalavasis, Karbasi A, A. Krause, V. Mirrokni, and G. Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representations, ICLR 2023, 2023 . OpenReview.net, 2023

2023
[32]

Esfandiari, A

H. Esfandiari, A. Karbasi, V. Mirrokni, G. Velegkas, and F. Zhou. Replicable clustering. Advances in Neural Information Processing Systems , 36:39277--39320, 2023

2023
[33]

Goldreich and D

O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, T...

2011
[34]

Guruswami

V. Guruswami. Rapidly mixing markov chains: A comparison of techniques (A survey). CoRR , abs/1603.01512, 2016

2016 arXiv
[35]

Hopkins, R

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

2024
[36]

Impagliazzo, R

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

2022
[37]

Kalavasis, A

A. Kalavasis, A. Karbasi, K. G. Larsen, G. Velegkas, and F. Zhou. Replicable learning of large-margin halfspaces. In Forty-first International Conference on Machine Learning , 2024

2024
[38]

Kalavasis, A

A. Kalavasis, A. Karbasi, S. Moran, and G. Velegkas. Statistical indistinguishability of learning algorithms. In International Conference on Machine Learning, ICML , 2023

2023
[39]

Karbasi, G

A. Karbasi, G. Velegkas, L. Yang, and F. Zhou. Replicability in reinforcement learning. Advances in Neural Information Processing Systems , 36:74702--74735, 2023

2023
[40]

Levin, Y

D. Levin, Y. Peres, and E. Wilmer. Markov Chains and Mixing Times . American Mathematical Society, 2006

2006
[41]

R. Levi, D. Ron, and R. Rubinfeld. Testing properties of collections of distributions. In ICS , pages 179--194, 2011

2011
[42]

Liu and C

S. Liu and C. Ye. Replicable uniformity testing. Advances in Neural Information Processing Systems , 37:32039--32075, 2024

2024
[43]

Moran, H

S. Moran, H. Schefler, and J. Shafer. The bayesian stability zoo. CoRR , abs/2310.18428, 2023

2023 arXiv
[44]

Paninski

L. Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory , 54(10):4750--4755, 2008

2008
[45]

Rubinfeld

R. Rubinfeld. Taming big probability distributions. XRDS: Crossroads, The ACM Magazine for Students , 19(1):24--28, 2012

2012
[46]

P. Valiant. Testing symmetric properties of distributions. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 383--392, 2008

2008
[47]

Valiant and P

G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing , 46(1):429--455, 2017

2017

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Acharya, H

J. Acharya, H. Das, A. Jafarpour, A. Orlitsky, and S. Pan. Competitive closeness testing. Journal of Machine Learning Research - Proceedings Track , 19:47--68, 2011

work page 2011

[2] [2]

Acharya, C

J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems , 28, 2015

work page 2015

[3] [3]

Aliakbarpour, I

M. Aliakbarpour, I. Diakonikolas, D. Kane, and R. Rubinfeld. Private testing of distributions via sample permutations. Advances in Neural Information Processing Systems , 32, 2019

work page 2019

[4] [4]

Aliakbarpour, I

M. Aliakbarpour, I. Diakonikolas, and R. Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In International Conference on Machine Learning , pages 169--178. PMLR, 2018

work page 2018

[5] [5]

Acharya, Z

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

work page 2018

[6] [6]

T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating entropy. In ACM Symposium on Theory of Computing , pages 678--687, 2002

work page 2002

[7] [7]

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. IEEE, 2001

work page 2001

[8] [8]

T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In 41st Annual Symposium on Foundations of Computer Science , 2000

work page 2000