arXiv preprint ·
High Probability Streaming Lower Bounds for $F_2$ Estimation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $δ$ remained open. We close this gap by proving a tight high-probability lower bound of $Ω\left(\frac{1}{\varepsilon^2}\log\frac{1}δ\,\log\frac{\varepsilon\sqrt{n}}{\log(1/δ)}\right)$ for $(1\pm\varepsilon)$-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 $Ω\left(\frac{m}{t}\log\frac{1}δ\right)$ 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_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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
A quantitative tree-likeness bound from average hyperbolicity
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.