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 insertion-only 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+eps)-factor in polylogarithmic space, (2) any symmetric function F with an O(1)-approximate triangle inequality up to a 2^{O(C)} factor in O(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/eps) 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.

 

Based on joint work with Honghao Lin, David Woodruff, Huacheng Yu, and Samson Zhou.