Metraipolis › archive › dc_d41e2149be3c

An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting — arXiv:2609.28528

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.28528
License (as archived)
CC0-1.0
Archived
2026-10-08T04:53:14.870Z
SHA-256 of the archived text
4e43ba88a157963c56a825774a7bec8fefd5adbbe4609b495dc9acc919bbd164
Stable URL of this page
https://metraipolis.com/documento/dc_d41e2149be3c

How to cite

An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting — arXiv:2609.28528 — arXiv (en), https://arxiv.org/abs/2609.28528 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d41e2149be3c (Metraipolis archive dc_d41e2149be3c, sha256 4e43ba88a157963c56a825774a7bec8fefd5adbbe4609b495dc9acc919bbd164)
BibTeX
@misc{dcd41e2149be3c,
  title = {An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting — arXiv:2609.28528},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28528},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d41e2149be3c; sha256 4e43ba88a157963c56a825774a7bec8fefd5adbbe4609b495dc9acc919bbd164},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.28528. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(\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 $\Omega(\log^{2}(n))$ for pure-differential private continual counting as well. They have subsequently published their $\Omega(\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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-25 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR) ; Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.28528 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T04:30:43.783Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).