# Replicable Distribution Testing

arXiv: https://arxiv.org/abs/2507.02814 · HTML: https://mlsanity.com/paper/2507.02814/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 49 references that are in the map.
- First posted on arXiv 3 Jul 2025.

## Builds on (most cited first, 28 of 28)

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions](https://mlsanity.com/paper/1508.05538/) (2015)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [Near-Optimal Closeness Testing of Discrete Histogram Distributions](https://mlsanity.com/paper/1703.01913/) (2017)
- [Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)](https://mlsanity.com/paper/1603.01512/) (2016)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)

## Built on by (most cited first, 2 of 2)

- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)

## Abstract (arXiv)

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.