# Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters

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

## Key facts

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

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

- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Machine Unlearning of Federated Clusters](https://mlsanity.com/paper/2210.16424/) (2022)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Federated Analytics: A survey](https://mlsanity.com/paper/2302.01326/) (2023)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors](https://mlsanity.com/paper/2503.11897/) (2025)

## Abstract (arXiv)

We consider the problems of distribution estimation and heavy hitter (frequency) estimation under privacy and communication constraints. While these constraints have been studied separately, optimal schemes for one are sub-optimal for the other. We propose a sample-optimal varepsilon-locally differentially private (LDP) scheme for distribution estimation, where each user communicates only one bit, and requires no public randomness. We show that Hadamard Response, a recently proposed scheme for varepsilon-LDP distribution estimation is also utility-optimal for heavy hitter estimation. Finally, we show that unlike distribution estimation, without public randomness where only one bit suffices, any heavy hitter estimation algorithm that communicates o(min log n, log k) bits from each user cannot be optimal.