What the study found
The authors present an algorithm for releasing a pure differentially private sparse histogram for n participants over a domain much larger than n. They report that it achieves the optimal ℓ∞-estimation error and runs in strictly O(n) time in the Word-RAM model.
Why the authors say this matters
The study suggests this breaks the previous deterministic-time quadratic barrier and resolves an open problem identified by Balcer and Balcer in 2019. The authors also say the algorithm can be implemented as an efficient circuit, enabling a first near-linear communication and computation cost pure DP histogram MPC protocol with optimal ℓ∞-estimation error.
What the researchers tested
The researchers designed an algorithm for pure differential privacy under the replacement neighboring relation. They also describe a circuit implementation and a private item blanket technique with target-length padding.
What worked and what didn't
The algorithm achieved the stated optimal ℓ∞-estimation error while using strictly O(n) time. It also admits an efficient circuit implementation, and the abstract says this enables near-linear communication and computation cost for a pure DP histogram MPC protocol.
What to keep in mind
The abstract does not describe experimental evaluation, numerical results, or practical constraints beyond the stated model assumptions. It also does not provide details on limitations outside the sparse histogram setting or the replacement neighboring relation.
Key points
- An algorithm is presented for pure differentially private sparse histograms.
- It is reported to achieve optimal ℓ∞-estimation error.
- The runtime is stated to be strictly O(n) in the Word-RAM model.
- The authors say it breaks a previous deterministic-time quadratic barrier.
- The abstract says the method supports an efficient circuit implementation for near-linear-cost pure DP histogram MPC.
Disclosure
- Research title:
- Optimal pure differentially private sparse histograms in linear time
- Image credit:
- Photo by Markus Spiske on Unsplash
Get the weekly research newsletter
Stay current with peer-reviewed research without reading academic papers — one filtered digest, every Friday.