Huacheng Yu

Elena Gribelyuk, Honghao Lin, David P. Woodruff et al.

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+\varepsilon)$-factor in polylogarithmic space, (2) any symmetric function $\cal{F}$ with an $\mathcal{O}(1)$-approximate triangle inequality up to a $2^{\mathcal{O}(C)}$ factor in $\tilde{\mathcal{O}}(n^{1/C}) \cdot S(n)$ bits of space, where $S$ is the space required to approximate $\cal{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 $\textrm{poly}((\log n)/\varepsilon)$ 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.

Cheng Jiang, Yinchen Liu, Huacheng Yu

A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LNW14] established an equivalence between the two, but their reduction requires a stream length that is at least doubly exponential in the dimension $n$. In the opposite direction, results by Kallaugher and Price [KP20] demonstrate a separation for streams of linear length, showing that the equivalence does not hold in general. The most natural and practically relevant regime -- polynomial-length streams -- has therefore remained open. We show that polynomial-length turnstile algorithms admit linear-sketch simulations. More precisely, if a turnstile algorithm uses $S$ bits of space and succeeds on all streams of length $\mathrm{poly}(D, n)$, then on final vectors $x$ with $\|x\|_2 \le D$, its output can be recovered from $O(S)$ linear measurements of $x$, using $O(S \log S)$ bits overall. For smooth problems under appropriate input distributions, a mollified version of the reduction yields a bounded-entry sketch with $O(S / \log D)$ measurements and optimal $O(S)$ total space. Our results extend to strict turnstile streams and non-uniform Read-Once Branching Programs (ROBPs). Our proof departs from prior transition-graph based machinery, relying instead on a Fourier-analytic framework and tools from additive combinatorics to extract discrete linear measurements. Our analysis shows that any $S$-bit algorithm can only be sensitive to a low-dimensional lattice of heavy Fourier frequencies, which we then use to construct the rows of the sketching matrix. Consequently, we obtain new lower bounds for polynomial-length streams via existing real sketching and communication lower bounds.