Adaptively Robust Resettable Streaming

We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. This model is suitable for applications such as active resource monitoring with support for deletions and machine unlearning. We show that all existing sketches for this model are vulnerable to adaptive adversarial attacks that apply even when the sketch size is polynomial in the length of the stream. To overcome these vulnerabilities, we present the first adaptively robust sketches for resettable streams that require only polylogarithmic space complexity in the stream length. Our framework supports (sub) linear statistics including $L_p$ moments for $p\in[0,1]$ (in particular, Cardinality and Sum) and Bernstein statistics. We bypass strong impossibility results known for linear and composable sketches by designing dedicated single-stream sketches robustified via Differential Privacy. Unlike standard robustification techniques, which provide limited benefits in this setting and still require polynomial space in the stream length, we leverage the Binary Tree Mechanism for continual observation to protect the sketch's internal randomness. This enables accurate prefix-max error guarantees with polylogarithmic space.

In the resettable streaming model, the input stream consists of a sequence of updates which may increase the value of a key or reset the current value to zero. Although streaming algorithms are often designed and analyzed under the assumption that the input is fixed in advance and independent of the randomness used by the algorithm, many practical applications require a more flexible model, where previous algorithm outputs may influence future inputs given to the algorithm. Motivated by this, we study several fundamental statistical estimation problems in the resettable streaming model under adaptive inputs and design the first polylogarithmic space sketches for cardinality and sum estimation, as well as a variety of other estimation tasks.