Please note: This seminar will take place in MC 2034 and online.
Elena Gribelyuk, PhD student
Department of Computer Science, Princeton University
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.
To attend this seminar in person, please go to MC 2034. You can also attend virtually on Zoom.