{"ID":6023596,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T14:11:27.630055639Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06312","arxiv_id":"2607.06312","title":"Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams","abstract":"We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1+ε)$-approximation for the second moment $F_2$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a major open question; for $p\\in[0,2)$, including the fundamental distinct elements problem ($F_0$), only constant-factor approximations were known in sublinear space. We close this gap, showing that $(1+ε)$-approximate robustness can be achieved in polylogarithmic space for all $p\\in[0,2]$. Our approach generalizes the estimator-corrector-learner framework to non-Hilbert spaces by dynamically maintaining implicit isometric embeddings into $L_2$ and performing regularized kernel ridge regression over adaptively discovered hard queries, yielding the first insertion-deletion algorithms that approximate: (1) the $p$-th frequency moment $F_p$ up to a $(1+ε)$-factor in poly$(1/ε, \\log n)$ space for all $p\\in[0,2]$, including the support size $F_0$, (2) metric and information-theoretic quantities, including the Earth Mover Distance (EMD) and $k$-median clustering cost over $[Δ]^d$ up to an $O(d \\log Δ)$-factor, and the Shannon entropy up to an $ε$-additive error, and (3) non-normed symmetric losses defined by Bernstein functions up to a $(1+ε)$-factor. For the $F_p$ moments, our algorithm is optimal up to poly$(1/ε, \\log n)$ factors. Furthermore, we establish a weak equivalence between classical oblivious sketching and adversarial robustness. We prove that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.","short_abstract":"We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust $(1+ε)$-approximation for the second moment $F_2$ in polylogarithmic space, achieving high accuracy for other frequency moments remained a m...","url_abs":"https://arxiv.org/abs/2607.06312","url_pdf":"https://arxiv.org/pdf/2607.06312v1","authors":"[\"Elena Gribelyuk\",\"Honghao Lin\",\"David P. Woodruff\",\"Huacheng Yu\",\"Samson Zhou\"]","published":"2026-07-07T14:15:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}