# The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting

arXiv: https://arxiv.org/abs/2607.00876 · HTML: https://mlsanity.com/paper/2607.00876/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 30 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Builds on (most cited first, 17 of 17)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Differentially Private Algorithms for Graphs Under Continual Observation](https://mlsanity.com/paper/2106.14756/) (2021)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [On Differentially Private Counting on Trees](https://mlsanity.com/paper/2212.11967/) (2022)
- [Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation](https://mlsanity.com/paper/2306.06723/) (2023)
- [CountSketches, Feature Hashing and the Median of Three](https://mlsanity.com/paper/2102.02193/) (2021)
- [Continual Counting with Gradual Privacy Expiration](https://mlsanity.com/paper/2406.03802/) (2024)
- [Private Counting of Distinct Elements in the Turnstile Model and Extensions](https://mlsanity.com/paper/2408.11637/) (2024)
- [Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model](https://mlsanity.com/paper/2505.23682/) (2025)

## Built on by (most cited first, 1 of 1)

- [Machine Unlearning as Private Retroactive Algorithms](https://mlsanity.com/paper/2609.05329/) (2026)

## Abstract (arXiv)

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. For fixed privacy parameters, the standard binary tree mechanism achieves expected ℓ_∞ error O(log3/2 n) under approximate differential privacy and O(log2 n) under pure differential privacy. Whether these dependences on the stream length are necessary has remained a central open problem. For fixed varepsilon∈(0,1), we prove a lower bound of Omega(log3/2 n) under approximate DP with sufficiently small fixed δ>0, and a lower bound of Omega(log2 n) under pure DP. These bounds establish the optimality of the binary tree mechanism in both settings. The bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. Both proofs use the same decomposition and accumulation of residual noise along a tree. As a consequence of the approximate-DP bound, we also obtain a largest-possible separation between hereditary discrepancy and private ℓ_∞ 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.