# Test without Trust: Optimal Locally Private Distribution Testing

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2018.

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

- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [Near-optimal algorithms for private estimation and sequential testing of collision probability](https://mlsanity.com/paper/2504.13804/) (2025)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [Near-Optimal Private Tests for Simple and MLR Hypotheses](https://mlsanity.com/paper/2601.21959/) (2026)
- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)

## Abstract (arXiv)

We study the problem of distribution testing when the samples can only be accessed using a locally differentially private mechanism and focus on two representative testing questions of identity (goodness-of-fit) and independence testing for discrete distributions. We are concerned with two settings: First, when we insist on using an already deployed, general-purpose locally differentially private mechanism such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data, and must build our tests based on the data collected via this mechanism; and second, when no such restriction is imposed, and we can design a bespoke mechanism specifically for testing. For the latter purpose, we introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We propose tests based on these mechanisms and analyze their sample complexities. Each proposed test can be implemented efficiently. In each case (barring one), we complement our performance bounds for algorithms with information-theoretic lower bounds and establish sample optimality of our proposed algorithm. A peculiar feature that emerges is that our sample-optimal algorithm based on RAPTOR uses public-coins, and any test based on RAPPOR or Hadamard Response, which are both private-coin mechanisms, requires significantly more samples.