Skirting Additive Error Barriers for Private Turnstile Streams

Anders Aamand, Justin Y. Chen, Sandeep Silwal · 2026

Read Skirting Additive Error Barriers for Private Turnstile Streams by Anders Aamand, Justin Y. Chen, Sandeep Silwal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10360.txt.

Description

Private continual release of distinct-item counts in turnstile streams, where items insert and delete, carries a polynomial additive error floor that has seemed fundamental. A 2026 paper led by Anders Aamand, with two co-authors, shows that floor can be dodged by letting estimates with both additive and multiplicative error. It reaches polylogarithmic multiplicative and additive error for continual distinct-element counts.

A similar pattern holds for the second frequency moment of a turnstile stream, reaching near-one multiplicative and polylogarithmic additive error. Both results use polylogarithmic space where prior approaches used polynomial space. With sublinear space, some multiplicative error is needed even without privacy, and the paper raises open questions on additive-multiplicative error trade-offs in private continual release.

Catalog record

CREATORAnders Aamand, Justin Y. Chen, Sandeep Silwal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10360

Browse the full library · About the Tower of Babel