Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time

Florian Kerschbaum, Steven Lee, Hao Wu

We present an algorithm that releases a pure differentially private (under the replacement neighboring relation) sparse histogram for $n$ participants over a domain of size $d \gg…