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 landmark work of Li, Nguyen, and Woodruff [LN…