Adaptively Robust Resettable Streaming

Edith Cohen, Elena Gribelyuk, Jelani Nelson, Uri Stemmer · 2026

Read Adaptively Robust Resettable Streaming by Edith Cohen, Elena Gribelyuk, Jelani Nelson, Uri Stemmer (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-2601-21989.txt.

Description

Edith Cohen, Elena Gribelyuk, Jelani Nelson, and Uri Stemmer study streaming algorithms that can forget. In the resettable streaming model, data arrive as a stream, and the value of each key can grow or be reset to zero. The model fits live resource monitoring that supports deletions, and machine unlearning.

The team's 2026 preprint develops adaptively robust methods for this model. Adaptive robustness is a strong demand. The algorithm must keep its guarantees even when future inputs react to its earlier outputs. That is much harder than handling a fixed stream. Guarantees like this matter for monitoring systems that adversaries, or simply responsive users, can probe and steer.

Catalog record

CREATOREdith Cohen, Elena Gribelyuk, Jelani Nelson, Uri Stemmer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21989

Browse the full library · About the Tower of Babel