# Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication

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

## Key facts

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

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

- [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)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Privacy-Aware Compression for Federated Data Analysis](https://mlsanity.com/paper/2203.08134/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [XRand: Differentially Private Defense against Explanation-Guided Attacks](https://mlsanity.com/paper/2212.04454/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (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)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansion](https://mlsanity.com/paper/2509.19661/) (2025)
- [High-Probability Bounds For Heterogeneous Local Differential Privacy](https://mlsanity.com/paper/2510.11895/) (2025)
- [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)
- [Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy](https://mlsanity.com/paper/2607.27815/) (2026)

## Abstract (arXiv)

We study the problem of estimating k-ary distributions under varepsilon-local differential privacy. n samples are distributed across users who send privatized versions of their sample to a central server. All previously known sample optimal algorithms require linear (in k) communication from each user in the high privacy regime (varepsilon=O(1)), and run in time that grows as n· k, which can be prohibitive for large domain size k. We propose Hadamard Response (HR, a local privatization scheme that requires no shared randomness and is symmetric with respect to the users. Our scheme has order optimal sample complexity for all varepsilon, a communication of at most log k+2 bits per user, and nearly linear running time of tildeO(n + k). Our encoding and decoding are based on Hadamard matrices, and are simple to implement. The statistical performance relies on the coding theoretic aspects of Hadamard matrices, ie, the large Hamming distance between the rows. An efficient implementation of the algorithm using the Fast Walsh-Hadamard transform gives the computational gains. We compare our approach with Randomized Response (RR), RAPPOR, and subset-selection mechanisms (SS), both theoretically, and experimentally. For k=10000, our algorithm runs about 100x faster than SS, and RAPPOR.