High Probability Streaming Lower Bounds for $F_2$ Estimation

Abstract

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 2025] resolved the space complexity for constant failure probability in the insertion-only model, the optimal dependence on the failure parameter $\delta$ remained open. We close this gap by proving a tight high-probability lower bound of $\Omega \left(\frac{1}{{\epsilon }^2}\log \frac{1}{\delta }\log \frac{\epsilon \sqrt{n}}{\log (1/\delta )}\right)$ for $(1\pm \epsilon )$-approximate $F_2$ estimation. The key challenge is the failure of prior multi-scale direct sum arguments under noise sensitivity. We introduce a noise-robust communication primitive, Exam Mostly Set Disjointness, and prove an $\Omega \left(\frac{m}{t}\log \frac{1}{\delta }\right)$ one-way lower bound. Embedding this into a multi-scale reduction yields the correct $\log (1/\delta )$ dependence. We also give two complementary algorithms under natural structure assumptions. For streams with frequency bound $B$, we design a subsampling method using continuous $F_0$ tracking that replaces a $\log (n)$ factor with $\text{polylog}(B)$. For $k$-sparse streams, we develop a two-stage sketch using approximate Morris counters, replacing $\log n$ with $\log k$ and achieving a further $\log \log m$ dependence on stream length.

arXiv commentRANDOM 2026