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

Referee: Main theorem (Fourier reduction): The claim that any S-bit poly-length algorithm is sensitive only to an O(S)-dimensional lattice of heavy frequencies is load-bearing. The argument must explicitly use the poly(D, n) length bound and additive combinatorics (e.g., a Freiman-type theorem or dimension bound on sumsets) to show that the lattice dimension cannot grow with the number of distinct updates or cancellations; without a concrete lemma proving dim = O(S) rather than O(poly(log D)) or worse, the fixed O(S)-row sketching matrix cannot be extracted.

Authors: We agree that an explicit dimension bound is essential for the main theorem. In our Fourier-analytic framework, the polynomial stream length bound is used to control the evolution of the frequency support: each update can introduce or cancel frequencies, but the total number of significant changes is limited by poly(D,n). Combined with additive combinatorics, specifically a version of Freiman's theorem applied to the sumset of heavy frequencies (which has small doubling due to the algorithm's limited space S), we show that the frequencies lie in a coset of a lattice of dimension O(S). We will insert a dedicated lemma (new Lemma 3.4) that states: If an S-bit algorithm processes a stream of length at most poly(D,n), then the set of heavy Fourier frequencies (with |hat f| > 2^{-O(S)}) generates a lattice of dimension at most 2S. This prevents growth beyond O(S) and allows extraction of the O(S) sketching rows. The proof of this lemma appears in the revised Section 3.2. revision: partial

Referee: Recovery procedure and error analysis: The statement that the output is recoverable from O(S) measurements with O(S log S) bits total lacks any quantitative success probability, approximation factor, or dependence on D and n. Because the original algorithm succeeds with high probability over all poly-length streams, the simulation must inherit explicit error bounds; their absence makes it impossible to verify that the linear-sketch simulation preserves the original guarantee.

Authors: We appreciate this observation regarding the need for quantitative guarantees. The recovery procedure involves identifying the O(S) heavy frequencies from the lattice and solving the resulting linear system to reconstruct the algorithm's state. Since the original algorithm succeeds with probability 1-δ over any poly-length stream, our simulation inherits this by union bound over the O(S) measurements, each of which can be estimated to sufficient precision using O(log S) bits. We will add an explicit error analysis in Section 4, stating that the simulation recovers the output with probability at least 1-δ, with additive error o(1) in the output (assuming the original is exact or approximate), and the total space remains O(S log S) with no additional dependence on D or n beyond the polynomial stream length assumption. This ensures the linear-sketch simulation preserves the original success guarantee. revision: yes

Referee: Mollified reduction for smooth problems: The improvement to O(S / log D) measurements is stated only for 'smooth problems under appropriate input distributions.' The precise definition of smoothness, the required distributional assumptions, and how they interact with the ||x||_2 ≤ D bound and the lattice extraction must be stated formally; otherwise the claimed space optimality cannot be assessed.

Authors: We concur that the mollified reduction requires a formal treatment. We define a problem as (β, γ)-smooth if for any two vectors x, x' with ||x - x'||_2 ≤ β, the output distributions differ by at most γ in total variation, under the input distribution. The appropriate distributions are those satisfying sub-Gaussian tails and bounded ||x||_2 ≤ D, which ensure that the heavy frequencies are concentrated and their lattice has effective dimension reduced by a log D factor due to concentration inequalities. We will formalize this in a new subsection (Section 5.1), including how the ||x||_2 ≤ D bound scales the frequencies and interacts with the lattice extraction to yield O(S / log D) measurements. The total space remains O(S) as the mollification uses bounded-entry sketches. This establishes the space optimality for such smooth problems. revision: yes