Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length 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 work of Li, Nguyen, and Woodruff (STOC~2014)…