High Probability Streaming Lower Bounds for F₂ Estimation
William Swartworth, David P. Woodruff, Samson Zhou · arXiv (Cornell University) · 2011
Estimating the second frequency moment (F₂) 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 δ remained open. We close this gap by proving a tight high-probability lower bound of Ω(1/ε² log(1/δ) log(ε√n) / log(1/δ)) for (1±ε)-approximate F₂ 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 Ω(m/t log(1/δ)) one-way lower bound. Embedding this into a multi-scale reduction yields the correct log(1/δ) 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₀ tracking that replaces a log n factor with log 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.