Search papers, labs, and topics across Lattice.
This paper establishes that the binary tree mechanism is asymptotically optimal for approximate differential privacy in continual counting, demonstrating that any differentially private mechanism must incur an expected $\ell_\infty$ error of at least $惟(\log^{3/2} n)$. The authors resolve a long-standing question regarding the necessity of this dependence on the stream length, thereby confirming the efficiency of the binary tree mechanism. Additionally, they reveal the largest possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, affirming the optimality of existing upper bounds.
Every differentially private mechanism for continual counting faces a fundamental limit: an expected $\ell_\infty$ error of at least $惟(\log^{3/2} n)$.
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.
