3 papers
cs.DS2025
Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time
Florian Kerschbaum, Steven Lee, Hao Wu
We present an algorithm that releases a pure differentially private (under the replacement neighboring relation) sparse histogram for participants over a domain of size $d \gg…
cs.CR2024
Faster Differentially Private Top- Selection: A Joint Exponential Mechanism with Pruning
Hao WU, Hanwen Zhang
We study the differentially private top- selection problem, aiming to identify a sequence of items with approximately the highest scores from items. Recent work by Gille…
cs.CC2024
A nearly- depth lower bound for formulas with restriction on top
Hao Wu
One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the versus pr…