Pith. sign in

REVIEW 1 minor 2 cited by

Any approximate differentially private mechanism for continual counting must incur expected ℓ_∞ error Ω(log^{3/2} n)

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Proves that the binary tree mechanism achieves the asymptotically optimal expected l_infty error of Theta(log^{3/2} n) for approximate DP continual counting.

T0 review reviewed 2026-07-03 challenge →

load-bearing objection This paper closes the open question by proving a matching Ω(log^{3/2} n) lower bound on expected ℓ_∞ error for any approximate-DP continual counting mechanism.

arxiv 2607.00876 v2 pith:Z2YTNX4A submitted 2026-07-01 cs.DS cs.CRcs.LG

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

Konstantina Bairaktari , Kasper Green Larsen This is my paper
classification cs.DS cs.CRcs.LG
keywords approximate differential privacycontinual countingbinary tree mechanismlower boundshereditary discrepancylinear queriesstreaming algorithms
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that no approximate differentially private algorithm for releasing all prefix counts on a binary stream of length n can achieve better than Ω(log^{3/2} n) expected maximum error. This matches the known upper bound achieved by the binary tree mechanism, which adds Gaussian noise scaled according to the depth in a binary tree representation of the stream. A sympathetic reader cares because the result settles whether the dependence on stream length is necessary and shows the standard algorithm cannot be improved asymptotically in the approximate-DP model. It further establishes that the known general upper bound on private error in terms of hereditary discrepancy is tight in its dependence on the number of queries.

Core claim

We resolve the dependence on n by proving that every differentially private mechanism for continual counting must incur expected ℓ_∞ 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 ℓ_∞ 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.

What carries the argument

The Ω(log^{3/2} n) lower bound on expected ℓ_∞ error for any approximate DP continual counting mechanism on binary streams

Load-bearing premise

The lower bound applies in the standard approximate differential privacy model on binary streams where each 1 comes from a distinct individual and error is measured in expected ℓ_∞ norm over all prefix counts.

What would settle it

An approximate differentially private mechanism for continual counting that achieves expected ℓ_∞ error o(log^{3/2} n) on binary streams of length n would falsify the lower bound.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The binary tree mechanism achieves the asymptotically optimal expected ℓ_∞ error for approximate DP continual counting.
  • The separation between hereditary discrepancy and private ℓ_∞ error for linear queries is the largest possible with respect to the number of queries.
  • The general upper bound on private ℓ_∞ error in terms of hereditary discrepancy has the optimal dependence on the number of queries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The lower bound technique may extend to other linear query problems under approximate differential privacy.
  • For very long streams the error scaling implies that practical deployments must tolerate growing error or use additional techniques such as user-level privacy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 1 minor

Summary. The paper proves that any (ε,δ)-DP mechanism for continual counting on binary streams of length n must incur expected ℓ_∞ error Ω(log^{3/2} n). This matches the upper bound of the Gaussian-noise binary tree mechanism, establishing asymptotic optimality for approximate DP. As a corollary, the work derives the largest separation between hereditary discrepancy and private ℓ_∞ error for linear queries.

Significance. If the lower-bound proof holds, the result resolves a central open question on the stream-length dependence for approximate-DP continual counting and supplies the tightest known separation result for private linear queries. The manuscript delivers a matching lower bound against a known upper bound together with a clean model statement (distinct individuals, prefix sums, expected ℓ_∞ norm), which are concrete strengths.

minor comments (1)
  1. [Abstract / §1] The abstract states the lower bound directly; the introduction or §2 should explicitly restate the precise model (binary stream, distinct individuals, expected ℓ_∞ error) to make the claim self-contained for readers who skip the full proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading, positive summary, and recommendation to accept the manuscript. The report identifies no major comments or concerns requiring response.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a lower bound of Ω(log^{3/2} n) on expected ℓ_∞ error for any (ε,δ)-DP mechanism for continual counting on binary streams. This matches the known upper bound achieved by the pre-existing binary tree mechanism (a standard construction not originating in this work). The derivation is a self-contained proof in the standard approximate-DP model with distinct individuals and prefix-sum queries; it contains no self-definitional reductions, fitted inputs renamed as predictions, load-bearing self-citations, or ansatz smuggling. The central claim is externally falsifiable against the binary-tree upper bound and does not reduce to the paper's own equations by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities. The claim rests on the standard model of approximate differential privacy and the binary-stream continual counting setting.

reviewed 2026-07-03 · how reviews work

0 comments
Cite this review

Pith. "Pith review of The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting." pith.science (2026). https://pith.science/paper/Z2YTNX4A

@misc{pith2026260700876,
  author       = {Pith},
  title        = {Pith review of: The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z2YTNX4A}},
  note         = {Machine review of arXiv:2607.00876}
}
Share X Bluesky LinkedIn Reddit HN
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 $\Omega(\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.

Figures

Figures reproduced from arXiv: 2607.00876 by Kasper Green Larsen, Konstantina Bairaktari.

Figure 1
Figure 1. Figure 1: Binary tree basis for n = 8. Filled nodes are the root or right children and have a χ u vector defined, shown with its binary indicator string. Empty nodes are left children and have no χ u vector. For clarity, each vector χ u in this figure uses the range of leaves in the subtree rooted at u to denote u, e.g. the root has χ 1−8 . The depth of the tree level is denoted by d. The reason for using this basis… view at source ↗
Figure 2
Figure 2. Figure 2: Adversary at node u ∈ T (which may or may not be in V(T )): given the noise ∆<ℓ(u) (z) and ∆<r(u) (z) in the two subtrees, the adversary computes mu and subtracts it from br(u) + xi · 1{r(u) ∈ I(i)} to obtain a residual σu. Noise Prediction via Grandchildren. Consider again a non-leaf node u and assume the children of u are also internal nodes. Instead of arguing that max<u(z) − min<u(z) grows compared to … view at source ↗
Figure 3
Figure 3. Figure 3: Case ℓ at a node u of even depth: given the noise ∆<ℓ(ℓ(u))(z) and ∆<ℓ(r(u))(z) in the two left grandchildren’s subtrees (solid), the adversary predicts br(u) with residual noise σu,ℓ. The right grandchil￾dren’s subtrees (dashed) need not be known. Averaging (4) and (5), we conclude E[max<u(z) − min<u(z)] ≥ σu,ℓ/2 + σu,r/2 + X f,g∈{ℓ,r} E h max<f(g(u))(z) − min<f(g(u))(z) i 4 . Starting from the root, whic… view at source ↗
Figure 4
Figure 4. Figure 4: Case r at a node u of even depth: given the noise ∆<r(ℓ(u))(z) and ∆<r(r(u))(z) in the two right grandchildren’s subtrees (solid), the adversary predicts br(ℓ(u)) − br(u) − br(r(u)) with residual noise σu,r. The left grandchildren’s subtrees (dashed) need not be known. let T s be the subset of T defined as follows. Starting from the root, from a node at an even depth 2d we descend into both children, and f… view at source ↗
Figure 5
Figure 5. Figure 5: The subtree T s for s = rr in a binary tree of height h = 4. Nodes in T s ∩ V(T ) are filled black, nodes in T s \ V(T ) have a solid white border, and nodes not in T s have a dashed border. For each node u ∈ T s at even depth (d = 0 and d = 2), both children of u are included in T s . For each node u at odd depth (d = 1 and d = 3), only the right child of u is included. The highlighted leaves give L(T s )… view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

    cs.CR 2026-07 reject novelty 7.0

    For the pure-DP Laplace matrix mechanism on prefix sums, the paper claims optimized maximum and mean squared errors of order Θ(log^3 n / ε^2) for arbitrary real factorizations, matching the best-known upper bound.

  2. Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization

    cs.DS 2026-07 accept novelty 7.0

    Recursive matrix factorization from optimized low-dimensional bases yields pure-DP continual counting with MaxSE ≤ 0.0778 log^{3}_{2} n/ε^{2} and MeanSE ≤ 0.0710 log^{3}_{2} n/ε^{2}, plus Ω(log^{3} n) lower bounds for...

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 2 Pith papers

  1. [1]

    Private stochastic convex optimiza- tion: Optimal rates in L1 geometry

    [AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in L1 geometry. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 ofProceedings of Machine Learning Research, pages 393–...

    work page 2021

  2. [2]

    Continual counting with gradual privacy expiration

    [AHP+24] Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, and Jalaj Upad- hyay. Continual counting with gradual privacy expiration. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 37: Annual Conference on...

    work page 2024

  3. [3]

    Improved counting under continual observation with pure differential privacy.CoRR, abs/2408.07021,

    [APT24] Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy.CoRR, abs/2408.07021,

    work page arXiv

  4. [4]

    The price of differential privacy for online learning

    [AS17] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 ofProceedings of Machine Learning Research, pages 32–40. PMLR,

    work page 2017

  5. [5]

    [CDP+24] Christopher A

    Association for Computing Machinery. [CDP+24] Christopher A. Choquette-Choo, Krishnamurthy Dj Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. InThe Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Au...

    work page 2024

  6. [6]

    Differentially private space-efficient algorithms for counting distinct elements in the turnstile model

    [CEM+25] Rachel Cummings, Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, and Peilin Zhong. Differentially private space-efficient algorithms for counting distinct elements in the turnstile model. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors,Forty-se...

    work page 2025

  7. [7]

    Lower bounds for dif- ferential privacy under continual observation and online threshold queries

    [CLN+24] Edith Cohen, Xin Lyu, Jelani Nelson, Tam´ as Sarl´ os, and Uri Stemmer. Lower bounds for dif- ferential privacy under continual observation and online threshold queries. In Shipra Agrawal and Aaron Roth, editors,The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, Proceedings of Machine Learning Resea...

    work page 2023

  8. [8]

    Hubert Chan, Elaine Shi, and Dawn Song

    28 [CSS10] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors,Automata, Languages and Programming, 37th International Collo- quium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, Le...

    work page 2010

  9. [9]

    [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors,Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, Lecture Notes in Computer Science, pages 265–284. Springer,

    work page 2006

  10. [10]

    Rothblum

    [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Leonard J. Schulman, editor,Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 715–724. ACM,

    work page 2010

  11. [11]

    Rothblum

    [DNRR15] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Tetsu Iwata and Jung Hee Cheon, editors,Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, Novemb...

    work page 2015

  12. [12]

    Differentially private algorithms for graphs under continual observation

    [FHO21] Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially private algorithms for graphs under continual observation. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors,29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conference), September 6-8, 2021, volume 204 ofLIPIcs, pages 42:1–42:16. Schlos...

    work page 2021

  13. [13]

    Constant matters: Fine-grained error bound on differentially private continual observation

    [FHU23] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,Interna- tional Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honol...

    work page 2023

  14. [14]

    Private streaming SCO inℓ p geometry with applications in high dimensional online decision making

    [HLL+22] Yuxuan Han, Zhicong Liang, Zhipeng Liang, Yang Wang, Yuan Yao, and Jiheng Zhang. Private streaming SCO inℓ p geometry with applications in high dimensional online decision making. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv´ ari, Gang Niu, and Sivan Sabato, editors,International Conference on Machine Learning, ICML 2022, 17-23...

    work page 2022

  15. [15]

    Efficient use of differentially private binary trees.Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27,

    [Hon15] James Honaker. Efficient use of differentially private binary trees.Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27,

    work page 2015

  16. [16]

    [HSS24] Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Private counting of distinct elements in the turnstile model and extensions. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, London School of Economics, London, UK, August 28-30, 2024, v...

    work page 2024

  17. [17]

    Almost tight error bounds on differentially private continual counting

    29 [HUU23] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5003–5039. SIAM,

    work page 2023

  18. [18]

    A unifying framework for differ- entially private sums under continual observation

    [HUU24] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for differ- entially private sums under continual observation. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 995–1018. SIAM,

    work page 2024

  19. [19]

    Counting distinct elements in the turnstile model with differential privacy under continual observation

    [JKR+23] Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neural Information Processing Systems 36: Annual ...

    work page 2023

  20. [20]

    Differentially private online learning

    [JKT12] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors,COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 24.1–24.34. JMLR.org,

    work page 2012

  21. [21]

    [JRSS23] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of dif- ferential privacy under continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors,International Confer- ence on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA...

    work page 2023

  22. [22]

    Practical and private (deep) learning without sampling or shuffling

    [KMS+21] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Res...

    work page 2021

  23. [23]

    Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020(3):751–780, 02

    [MNT20] Jir´ ı Matousek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020(3):751–780, 02

    work page 2020

  24. [24]

    The geometry of differential privacy: the sparse and approximate cases

    [NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 351–360. ACM,

    work page 2013

  25. [25]

    Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2733–2741,

    work page 2013

This paper was first reviewed by grok-4.3 on July 3, 2026.