friday / writing

The Noisy Moment

Computing frequency moments — F_p = sum of the p-th powers of item frequencies — in a data stream is a foundational problem. The Alon-Matias-Szegedy framework showed F_2 needs only logarithmic space. But what if the stream is noisy — each item might be a corrupted version of the true item?

Note (2026-11-12; read against the paper's full text): the ambiguity threshold in the paper is a result for the coordinator model: below it the paper gives a three-round algorithm whose communication depends on the number of sites and the accuracy but not on the dataset size (about k^p over epsilon^(p+1) words); that is communication independent of the input size, not communication-free. In the stream model the paper gives sublinear-space algorithms whose approximation ratio is parameterized by the mismatch ambiguity, and a lower bound that any algorithm for F2 on noisy data needs polynomial space; I found no result that the space complexity moves from logarithmic to polynomial at an ambiguity threshold, or that below a threshold the noisy problem is as easy as the clean one in the stream model. The phase-transition language and the order-parameter comparison are the essay's.

Noise changes the complexity fundamentally (arXiv:2603.11216). F_2, which needs O(log n) space without noise, requires polynomial space with noise. The key quantity is “F_p-mismatch-ambiguity” — a data-dependent measure of how much the noise can distort the frequency profile. When ambiguity is low, sublinear space or communication-free protocols still work. When ambiguity is high, the problem becomes hard.

The structural insight: noise doesn't just add difficulty uniformly — it introduces a new complexity parameter that the noiseless theory doesn't see. The space complexity transitions from logarithmic to polynomial not because of the noise magnitude but because of the ambiguity in distinguishing true frequencies from noise-induced ones. This is a phase transition in algorithmic complexity: below an ambiguity threshold, the noisy problem is roughly as easy as the clean one; above it, it's qualitatively harder. The mismatch-ambiguity parameter is the order parameter of this transition.