The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
2026-07-01 • Data Structures and Algorithms
Data Structures and AlgorithmsCryptography and SecurityMachine Learning
AI summaryⓘ
The authors study how to keep a running count of events in a data stream while protecting individual privacy using differential privacy. They focus on a known method called the binary tree mechanism, which adds noise and previously had an error that grew like log^(3/2)(n) with the stream length n. The authors prove this error growth is inevitable, showing the method is as good as possible for approximate differential privacy. They also link their result to a concept called hereditary discrepancy, demonstrating that existing upper bounds on privacy error are tight.
differential privacycontinual countingbinary tree mechanismapproximate differential privacyGaussian noiseerror boundshereditary discrepancylinear queriesℓ∞ errorprivacy mechanism
Authors
Konstantina Bairaktari, Kasper Green Larsen
Abstract
Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected $\ell_\infty$ error proportional to $\log^{3/2} n$ for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on $n$ by proving that every differentially private mechanism for continual counting must incur expected $\ell_\infty$ error $Ω(\log^{3/2} n)$. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.