# Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2020.

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

- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Token-Efficient Change Detection in LLM APIs](https://mlsanity.com/paper/2602.11083/) (2026)
- [Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates](https://mlsanity.com/paper/2211.08580/) (2022)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Distribution-Aware Mean Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2410.09506/) (2024)
- [Locally differentially private estimation of nonlinear functionals of discrete distributions](https://mlsanity.com/paper/2107.03940/) (2021)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)

## Abstract (arXiv)

We find separation rates for testing multinomial or more general discrete distributions under the constraint of local differential privacy. We construct efficient randomized algorithms and test procedures, in both the case where only non-interactive privacy mechanisms are allowed and also in the case where all sequentially interactive privacy mechanisms are allowed. The separation rates are faster in the latter case. We prove general information theoretical bounds that allow us to establish the optimality of our algorithms among all pairs of privacy mechanisms and test procedures, in most usual cases. Considered examples include testing uniform, polynomially and exponentially decreasing distributions.