EUVIMEDEUVIMED entdecken
Crossref

Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time

Florian Kerschbaum, Steven Lee, Hao Wu

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-27

DOI: 10.1145/3801909 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Florian Kerschbaum und 2 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 >> n . Our method achieves the optimal ℓ ∞ -estimation error and runs in strictly O ( n ) time in the Word-RAM model, improving upon the previous best deterministic-time bound of Õ ( n 2 ) and resolving the open problem of breaking this quadratic barrier (Balcer and Balcer 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 ℓ ∞ -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.

Zitieren

APA

Kerschbaum, F., Lee, S., & Wu, H. (2026). Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time. Proceedings of the ACM on Management of Data, 4(2), 1-27. https://doi.org/10.1145/3801909

Vancouver

Kerschbaum F, Lee S, Wu H. Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time. Proceedings of the ACM on Management of Data. 2026;4(2):1-27. doi:10.1145/3801909

BibTeX
@article{Kerschbaum2026,
  author = {Kerschbaum, Florian and Lee, Steven and Wu, Hao},
  title = {Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--27},
  doi = {10.1145/3801909}
}
Kostenlos starten →