A fundamental question in streaming complexity asks whether every space‑efficient turnstile algorithm is implicitly a linear sketch. Li, Nguyen and Woodruff (STOC 2014) proved an equivalence, but their reduction requires the stream length to be at least doubly exponential in the dimension $n$. In contrast, Kallaugher and Price (STOC 2020) exhibited a separation for streams of linear length, showing that the equivalence does not hold in general. Hence the most natural and practically relevant regime—polynomial‑length streams—has remained open.
We show that turnstile algorithms on polynomial‑length streams admit linear‑sketch simulations. More precisely, if a turnstile algorithm uses $S$ bits of space and succeeds on all streams of length $\operatorname{poly}(D, n)$, then for final vectors $x$ with $\|x\|_2 \le D$, its output can be recovered from $O(S)$ linear measurements of $x$, using $O(S)$ bits overall. For smooth problems under suitable input distributions, a mollified version of the reduction yields a bounded‑entry sketch with $O(S / \log D)$ measurements and optimal $O(S)$ total space.
Our results also extend to strict turnstile streams and non‑uniform read‑once branching programs (ROBPs). Instead of the transition‑graph arguments of prior work, the proof relies on Fourier analysis and tools from additive combinatorics to extract discrete linear measurements. We prove that an $S$‑bit algorithm can be sensitive only to a small set of heavy Fourier frequencies, which lie close to a finite group of order $2^{O(S)}$; the generators of this group serve as the rows of the sketching matrix.
Combined with existing lower bounds for real sketches and for communication, this yields new lower bounds for polynomial‑length turnstile streams.
Review