Adversarial Robustness on Insertion-Deletion Streams

We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for insertiononly streams with only a polylogarithmic overhead in memory over non-robust algorithms, it was widely conjectured that turnstile streams of length polynomial in the universe size n require space linear in n. We refute this conjecture, showing that robustness can be achieved using space which is significantly sublinear in n. Our framework combines multiple linear sketches in a novel estimator-corrector-learner framework, yielding the first insertion-deletion algorithms that approximate: (1) the second moment F 2 up to a (1 + ε)-factor in polylogarithmic space, (2) any symmetric function F with an O(1)-approximate triangle inequality up to a 2 O(C) factor in Õ(n 1/C ) • S(n) bits of space, where S is the space required to approximate F non-robustly; this includes a broad class of functions such as the L 1 -norm, the support size F 0 , and non-normed losses such as the M -estimators, and (3) L 2 heavy hitters. For the F 2 moment, our algorithm is optimal up to poly((log n)/ε) factors. Given the recent results of Gribelyuk et al. (STOC, 2025), this shows an exponential separation between linear sketches and non-linear sketches for achieving adversarial robustness in turnstile streams.