{"ID":2891982,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.17017","arxiv_id":"2507.17017","title":"Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time","abstract":"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 n$. Our method achieves the optimal $\\ell_\\infty$-estimation error and runs in strictly $O(n)$ time in the Word-RAM model, improving upon the previous best deterministic-time bound of $\\tilde{O}(n^2)$ and resolving the open problem of breaking this quadratic barrier (Balcer and Vadhan, 2019). Moreover, the algorithm admits an efficient circuit implementation, enabling the first near-linear communication and computation cost pure DP histogram MPC protocol with optimal $\\ell_\\infty$-estimation error. Central to our algorithm is a novel **private item blanket** technique with target-length padding, which hides differences in the supports of neighboring histograms while remaining efficiently implementable.","short_abstract":"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 n$. Our method achieves the optimal $\\ell_\\infty$-estimation error and runs in strictly $O(n)$ time in the Word-RAM model, improving upon th...","url_abs":"https://arxiv.org/abs/2507.17017","url_pdf":"https://arxiv.org/pdf/2507.17017v2","authors":"[\"Florian Kerschbaum\",\"Steven Lee\",\"Hao Wu\"]","published":"2025-07-22T21:17:59Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CR\"]","methods":"[]","has_code":false}