Optimal Pure Differentially Private Sparse Histograms in Near-Linear Deterministic Time

We introduce an algorithm that releases a pure differentially private sparse histogram over n participants drawn from a domain of size d n. Our method attains the optimal _∞-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 Õ(n²) 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.