# Tight Lower Bounds for Differentially Private Continual Counting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2026.

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

- [An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting](https://mlsanity.com/paper/2609.28528/) (2026)

## Abstract (arXiv)

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 ≤ 1, we prove asymptotically tight lower bounds of Omega(log2 n) for worst-case expected ℓ_∞ error and Omega(log3 n) for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever δ≤ n-c, for any fixed c>0. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of δ ll1/n. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.