Seminar • Algorithms and Complexity • Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time

Please note: This seminar will take place in DC 1304 and online.

Hao Wu, Postdoctoral Researcher
David R. Cheriton School of Computer Science

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)).

This seminar is based on the paper at https://arxiv.org/abs/2507.17017v2.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.