arXiv preprint ·
An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02) of the proof by Astra on the lower bound for differentially private continual counting. We believe a more natural and easy proof is possible and hope that this note will help in that effort. Prior to the initial preprint by Harrison and Leeman (arXiv:2609.17650v01), Bairaktari and Larsen (arXiv:2607.00876) gave an elegant proof to show a lower bound of $Ω(\log^{3/2}(n))$ for both pure and approximate-DP continual counting, and in personal communication had informed us that they have a proof of optimal $Ω(\log^{2}(n))$ for pure-differential private continual counting as well. They have subsequently published their $Ω(\log^{2}(n))$ bound, which is now a joint work of Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3). Their new result is an elegant extension of their technique for approximate-differential privacy. Although the two proofs are technically different, the Astra argument uses related tree geometry introduced in Bairaktari and Larsen.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Cryptography & Security
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Improved Algorithms for the Remote Point Problem
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Exponential Quantum Advantage in Testing Fourier Dimensionality
Get the few papers worth your time in Cryptography & Security every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.