2026-09-10T09:45:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27793 2026-09-09T12:19:39Z ddc:004 open_access

High Probability Streaming Lower Bounds for F₂ Estimation Swartworth, William Woodruff, David P. Zhou, Samson streaming algorithms lower bounds moment estimation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William Swartworth and David P. Woodruff and Samson Zhou 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.76 urn:nbn:de:0030-drops-277936 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.76 eng https://creativecommons.org/licenses/by/4.0/legalcode