Charlie Harrison

Tight Lower Bounds for Differentially Private Continual Counting

The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0<\varepsilon \le 1$, we prove asymptotically tight lower bounds of $\Omega(...