Elena Gribelyuk

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.