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?

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.