# A Locally Differential Private Coding-Assisted Succinct Histogram Protocol

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 13 references that are in the map.
- First posted on arXiv 21 Jun 2025.

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

- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Projective Systematic Authentication via Reed-Muller Codes](https://mlsanity.com/paper/2404.09088/) (2024)

## Abstract (arXiv)

A succinct histogram captures frequent items and their frequencies across clients and has become increasingly important for large-scale, privacy-sensitive machine learning applications. To develop a rigorous framework to guarantee privacy for the succinct histogram problem, local differential privacy (LDP) has been utilized and shown promising results. To preserve data utility under LDP, which essentially works by intentionally adding noise to data, error-correcting codes naturally emerge as a promising tool for reliable information collection. This work presents the first practical (ε,δ)-LDP protocol for constructing succinct histograms using error-correcting codes. To this end, polar codes and their successive-cancellation list (SCL) decoding algorithms are leveraged as the underlying coding scheme. More specifically, our protocol introduces Gaussian-based perturbations to enable efficient soft decoding. Experiments demonstrate that our approach outperforms prior methods, particularly for items with low true frequencies, while maintaining similar frequency estimation accuracy.