# Replicable Uniformity Testing

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 12 Oct 2024.

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

- [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)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (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)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [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)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (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)
- [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)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)

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

- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [SS-DC: Spatial-Spectral Decoupling and Coupling Across Visible-Infrared Gap for Domain Adaptive Object Detection](https://mlsanity.com/paper/2507.12017/) (2025)
- [Replicable Conformal Prediction](https://mlsanity.com/paper/2608.23638/) (2026)

## Abstract (arXiv)

Uniformity testing is arguably one of the most fundamental distribution testing problems. Given sample access to an unknown distribution p on [n], one must decide if p is uniform or varepsilon-far from uniform (in total variation distance). A long line of work established that uniformity testing has sample complexity Theta(√nvarepsilon-2). However, when the input distribution is neither uniform nor far from uniform, known algorithms may have highly non-replicable behavior. Consequently, if these algorithms are applied in scientific studies, they may lead to contradictory results that erode public trust in science. In this work, we revisit uniformity testing under the framework of algorithmic replicability [STOC '22], requiring the algorithm to be replicable under arbitrary distributions. While replicability typically incurs a ρ-2 factor overhead in sample complexity, we obtain a replicable uniformity tester using only tildeO(√n varepsilon-2 ρ-1) samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on ρ. Lastly, we consider a class of ``symmetric" algorithms [FOCS '00] whose outputs are invariant under relabeling of the domain [n], which includes all existing uniformity testers (including ours). For this natural class of algorithms, we prove a nearly matching sample complexity lower bound for replicable uniformity testing.