Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams

Source: arXiv:2604.22052 · Published 2026-04-23 · By Cheng Jiang, Yinchen Liu, Huacheng Yu

TL;DR

This paper addresses a structural question in turnstile streaming: when does a space-efficient streaming algorithm implicitly behave like a linear sketch? The classic equivalence of Li–Nguyen–Woodruff works for arbitrarily long streams, but it needs doubly exponential stream length; Kallaugher–Price later showed separations for linear-length streams. The open regime was polynomial-length streams, which is the practically relevant case for most dynamic-data applications.

The main result is a new transfer theorem: any S-bit turnstile algorithm that succeeds on all streams of length poly(D,n) can be simulated, on final vectors with |x|_2 \le D, by O(S) linear measurements using O(S log S) total bits; a mollified variant gives O(S/\log D) measurements and O(S) bits for smooth problems under suitable input distributions. The proof is not the old transition-graph/mixing argument; it is Fourier-analytic and additive-combinatorial. The authors show that the algorithm’s posterior distributions only have sensitivity on a low-dimensional lattice of heavy Fourier frequencies, and they extract those frequencies as rows of a sketching matrix. They then use this to derive new polynomial-length turnstile lower bounds by importing existing real-sketch and SMP lower bounds.

Key findings

• Polynomial-length turnstile algorithms using S bits can be simulated by linear sketches with O(S) measurements and O(S log S) bits on final vectors with |x|_2 \le D, assuming the stream length is poly(D,n).
• The exact transfer theorem extends beyond standard turnstile streams to strict turnstile streams and non-uniform Read-Once Branching Programs (ROBPs).
• For smooth problems under a distributional assumption, the mollified transfer reduces the sketch dimension to O(S/\log D) measurements while keeping total space O(S) bits and bounded integer entries poly(R).
• For (1+\epsilon)-approximate L_p estimation on unit-update streams of length W \ge poly(n/\delta), the paper derives lower bounds matching known upper-bound dependences on log W and, for p>2, on the mixed \epsilon and \delta terms stated in Theorem 1.3.
• For L_0 estimation, the paper proves an \Omega(\epsilon^{-2} \log n \cdot \log\log W / \log(\epsilon^{-2}\log n\log\log W)) lower bound, improving to \Omega(\epsilon^{-2}\log n\log\log W) when W is sufficiently large.
• For approximate maximum matching in strict turnstile streams, the paper obtains an \Omega(n^{2-3\epsilon-o(1)}) space lower bound.
• The proof yields new polynomial-length-stream lower bounds by plugging the transfer theorem into existing real-sketch lower bounds and public-coin SMP lower bounds; the paper explicitly cites L_p norms, operator/Ky Fan norms, eigenvalue approximation, PSD testing, compressed sensing, L_0 approximation, approximate maximum matching, maximum matching size, and subgraph counting as instantiations.
• The reduction preserves the natural dimension parameter more faithfully than the older LNW14/AHLW16 route, which can inflate dimension when moduli are small; this matters for approximation problems where sketch dimension, not total bits, is the key hardness measure.

Threat model

The adversary is a turnstile streaming algorithm that processes a one-pass sequence of updates and may use only S bits of memory; in the strict-turnstile and ROBP variants, the update rule may be more structured or non-uniform. The adversary is not assumed to know the random prefix updates in advance, but it may be randomized and is required to succeed on all streams of polynomial length reaching a given final vector. It cannot avoid the polynomial-length regime or rely on the long-stream mixing phenomena exploited by older equivalence proofs; the reduction explicitly targets the setting where the stream length is only poly(D,n).

Methodology — deep read

The paper’s adversary is a standard one-pass turnstile streaming algorithm with S bits of internal state, operating on integer frequency vectors under unit updates (or more generally bounded updates in the abstracted setup). The key assumption is polynomial stream length: the algorithm must succeed on all streams of length poly(D,n) for final vectors with |x|_2 \le D. Unlike earlier equivalence proofs, the argument does not assume a uniform transition function or a mixing process on the state graph. The goal is to show that, for any such algorithm, there exists a linear sketch whose kernel only contains directions along which the algorithm is essentially shift-invariant. In the strict-turnstile and ROBP extensions, the algorithm may have additional structure or non-uniform update rules, but the proof still only uses that every reachable final frequency vector is correctly handled on all polynomial-length streams reaching it.

The data distribution used in the core reduction is synthetic and distributional. The authors feed the algorithm a long prefix of independent increments X_1,\dots,X_M, each drawn from an n-dimensional discrete Gaussian \gamma_R with radius R=poly(n), and then append a final correction update y-X so the stream “lands” on a target vector y. This creates a random prefix whose total vector X=\sum_i X_i is highly diffused. Conditioning on the algorithm’s memory states \sigma_i after each prefix update yields posterior laws \mu_i=(X_i\mid \sigma_i). Because each \sigma_i is only S bits, a typical posterior has probability mass on at most 2^{O(S)} states, and the authors exploit this to treat \mu_i as a constrained perturbation of the original discrete Gaussian. They also work with a mollified setup for smooth problems: the target input distribution I is supported in an \ell_2 ball of radius R^{5/4}, and smoothness is defined by the property that Y\sim I and Z\sim\gamma_R satisfy |f(Y+Z)-f(Y)|\le \epsilon with probability at least 1-\delta.

The central algorithmic/mathematical object is the convolution \nu=\mu_1*\cdots*\mu_M, the distribution of the conditioned prefix sum. The authors analyze its Fourier transform on the torus T^n. For the idealized case where every \mu_i=\gamma_R, one has \widehat\nu(\zeta)=(\widehat{\gamma_R}(\zeta))^M\approx \exp(-\Theta(MR^2|\zeta|^2_{T^n}))), so high frequencies are strongly damped. In the actual conditioned setting, the authors develop a framework to identify the “heavy” Fourier frequencies that survive conditioning. The proof uses additive-combinatorics tools—most notably structure theorems for large spectra, dissociated sets, and a coarse Rudin inequality—to show that these heavy frequencies lie in a low-dimensional lattice structure. Intuitively, the algorithm can only preserve a small set of arithmetic obstructions, such as parity constraints or subspace constraints, and those obstructions can be encoded by a small matrix A whose rows span the relevant frequency lattice.

The technical bridge from Fourier control to total variation is carried out line-by-line. Rather than trying to bound |\nu-\tau_v\nu|1 directly in high dimension, the proof projects onto one-dimensional lines parallel to a candidate shift v and analyzes the induced 1D distributions \nu(t)=\nu(x+tv). The Fourier transform of each line marginal is an affine slice of \widehat\nu, so concentration of \widehat\nu near the origin implies small variation along each line. Parseval/Cauchy–Schwarz then yields a bound on the 1D total variation along that line, and summing over all parallel lines gives a global TV bound between \nu and its translate \tau_v\nu. If v is in the kernel of the extracted sketch matrix A, the argument shows that \nu and \tau_v\nu are close enough that the streaming algorithm cannot reliably distinguish landing at y_1 versus y_2=y_1-v; hence it must output the same value, forcing f(y_1)=f(y_2). This is the exact mechanism by which the sketch matrix is “decoded” from the algorithm’s state sensitivity.

Training in the ML sense is not relevant here; instead, the authors’ proof strategy is modular and layered. First they establish Fourier decay for discrete Gaussians and convolution products, then structural theorems for large Fourier spectra of conditioned pieces, then translation-invariance/total-variation bounds from line analysis, and finally transfer theorems that convert these analytic facts into sketching simulations. The paper states that the exact route produces O(S log S) total bits, while the mollified route removes that overhead under average smoothness assumptions. Reproducibility is theoretical rather than experimental: the paper is an arXiv proof paper, with theorems and detailed appendices, but no code, datasets, or empirical training artifacts. The abstract and introduction do not specify frozen weights or released artifacts because the results are not computational experiments.

Technical innovations

• A Fourier-analytic replacement for the LNW14/AHLW16 transition-graph/mixing reduction, tailored to polynomial-length streams.
• A heavy-Fourier-frequency structure theorem showing that an S-bit algorithm can only be sensitive to a low-dimensional lattice of frequencies.
• A line-by-line translation-invariance argument that converts spectral concentration into total-variation closeness for shifted conditioned prefix distributions.
• A mollified transfer theorem that yields bounded-entry sketches with O(S/\log D) measurements and O(S) bits for smooth problems.
• Extensions of the transfer framework to strict turnstile streams and non-uniform ROBPs.

Baselines vs proposed

• LNW14/AHLW16 equivalence: requires streams of length at least doubly exponential in n vs proposed: polynomial-length streams poly(D,n).
• Kallaugher-Price separation for linear-length streams: equivalence fails in general vs proposed: equivalence restored for polynomial-length streams.
• For L_p estimation (1\le p\le 2): previous exact-space and index-based lower bounds did not capture optimal log W dependence vs proposed: \Omega(min{\epsilon^{-2}\log(1/\delta),n}\cdot\log W).
• For L_p estimation (p>2): prior lower bounds lacked the full mixed \epsilon,\delta, and log W dependence vs proposed: \Omega(min{n^{1-2/p}\epsilon^{-2/p}\log n\log^{2/p}(1/\delta)+n^{1-2/p}\epsilon^{-2}\log(1/\delta),n}\cdot\log W).
• For L_0 estimation: KNW10 upper bound uses O(\epsilon^{-2}\log n(\log(1/\epsilon)+\log\log W)) bits vs proposed lower bound: \Omega(\epsilon^{-2}\log n\log\log W / \log(\epsilon^{-2}\log n\log\log W)).
• For sufficiently large W in L_0 estimation, the proposed lower bound becomes \Omega(\epsilon^{-2}\log n\log\log W), matching the best known upper bound up to constants in the stated regime.
• For approximate maximum matching: the paper gives a lower bound of \Omega(n^{2-3\epsilon-o(1)}) bits in strict turnstile streams; no direct baseline value is stated in the provided text.

Limitations

• The paper is theoretical; no empirical validation, implementation benchmarks, or runtime/memory measurements are provided.
• The main exact transfer theorem applies to streams of length poly(D,n), so the equivalence is not claimed for arbitrary or superpolynomially long streams.
• The mollified transfer requires a smoothness condition under a specific discrete-Gaussian perturbation and an input distribution I supported in an \ell_2 ball; it is not a worst-case statement.
• Several applications are inherited through existing lower-bound frameworks, so the new contribution is the transfer theorem rather than fresh problem-specific lower-bound proofs.
• The abstract says O(S log S) total bits for the exact transfer, which is an overhead compared with the source streaming space S; the paper also notes the O(S) space improvement only in the regime S=O(log R).
• The full proof relies on nontrivial Fourier/additive-combinatorics machinery, which may make the reduction hard to turn into a practical algorithmic transformation.

Open questions / follow-ons

• Can the O(S log S) overhead in the exact transfer be removed in full generality, without assuming mollification or smoothness?
• Is there a sharper characterization of the low-dimensional frequency lattice beyond the coarse heavy-spectrum structure used here, and can it yield tighter sketch dimension bounds?
• Do analogous polynomial-length equivalence results hold for broader update models, such as bounded modular updates or streaming with limited adaptivity beyond ROBPs?
• Can the line-by-line Fourier argument be adapted to obtain constructive, efficiently computable sketches rather than existential reductions?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, the paper is not about CAPTCHA systems directly, but it is relevant as a general lesson about structure extraction under limited memory. The proof shows that once an online process is forced to operate with small state on long enough random perturbations, its behavior can collapse onto a low-dimensional set of linear invariants. That is conceptually similar to how bot detectors often try to identify stable, low-entropy features from noisy interaction traces.

A practical takeaway is methodological: if your detection pipeline relies on a black-box stateful process, the paper suggests looking for hidden linear or lattice-like summaries that fully capture what the system can remember. Conversely, if you are designing defenses against adaptive bots, this kind of result is a reminder that streaming state alone may not buy you as much nonlinearity as it seems once the interaction horizon is polynomially long and the inputs are sufficiently smooth or randomized. The result is mainly a structural warning, not an implementable CAPTCHA recipe.

Cite

@article{arxiv2604_22052,
  title={ Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams },
  author={ Cheng Jiang and Yinchen Liu and Huacheng Yu },
  journal={arXiv preprint arXiv:2604.22052},
  year={ 2026 },
  url={https://arxiv.org/abs/2604.22052}
}

Read the full paper

• arXiv:2604.22052 (abstract)
• arXiv:2604.22052 (PDF)