Preprint
Jul 2026
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams
It is proved 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.
Elena Gribelyuk, Honghao Lin, David P. Woodruff et al.
· 0 citations