Optimal Pure Differentially Private Sparse Histograms in Near-Linear Deterministic Time
By: Florian Kerschbaum, Steven Lee, Hao Wu
Potential Business Impact:
Keeps data private while showing trends.
We introduce an algorithm that releases a pure differentially private sparse histogram over $n$ participants drawn from a domain of size $d \gg n$. Our method attains the optimal $\ell_\infty$-estimation error and runs in strictly $O(n \ln \ln d)$ time in the word-RAM model, thereby improving upon the previous best known deterministic-time bound of $\tilde{O}(n^2)$ and resolving the open problem of breaking this quadratic barrier (Balcer and Vadhan, 2019). Central to our algorithm is a novel private item blanket technique with target-length padding, which transforms the approximate differentially private stability-based histogram algorithm into a pure differentially private one.
Similar Papers
On Purely Private Covariance Estimation
Machine Learning (CS)
Keeps data private while still learning from it.
Differentially Private Community Detection in $h$-uniform Hypergraphs
Information Theory
Keeps private data safe when sharing network maps.
An Iconic Heavy Hitter Algorithm Made Private
Cryptography and Security
Finds important data privately and accurately.