# Uniformity Testing in the Shuffle Model: Simpler, Better, Faster

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 37 references that are in the map.
- First posted on arXiv 20 Aug 2021.

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

- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [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)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [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)
- [Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead](https://mlsanity.com/paper/2106.04247/) (2021)
- [Pure Differentially Private Summation from Anonymous Messages](https://mlsanity.com/paper/2002.01919/) (2020)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Differential Privacy in the Shuffle Model: A Survey of Separations](https://mlsanity.com/paper/2107.11839/) (2021)
- [Test without Trust: Optimal Locally Private Distribution Testing](https://mlsanity.com/paper/1808.02174/) (2018)
- [Inference under Information Constraints III: Local Privacy Constraints](https://mlsanity.com/paper/2101.07981/) (2021)
- [Connecting Robust Shuffle Privacy and Pan-Privacy](https://mlsanity.com/paper/2004.09481/) (2020)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [Locally Private Hypothesis Testing](https://mlsanity.com/paper/1802.03441/) (2018)
- [Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms](https://mlsanity.com/paper/2005.12601/) (2020)
- [Pan-Private Uniformity Testing](https://mlsanity.com/paper/1911.01452/) (2019)
- [Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit](https://mlsanity.com/paper/1907.08743/) (2019)

## Abstract (arXiv)

Uniformity testing, or testing whether independent observations are uniformly distributed, is the prototypical question in distribution testing. Over the past years, a line of work has been focusing on uniformity testing under privacy constraints on the data, and obtained private and data-efficient algorithms under various privacy models such as central differential privacy (DP), local privacy (LDP), pan-privacy, and, very recently, the shuffle model of differential privacy. In this work, we considerably simplify the analysis of the known uniformity testing algorithm in the shuffle model, and, using a recent result on "privacy amplification via shuffling," provide an alternative algorithm attaining the same guarantees with an elementary and streamlined argument.