Streaming Lower Bounds for the Needle Problems
summary
Shows a near-tight lower bound: any streaming algorithm with space s needs about t ≈ 1/(s p^2) samples (multipass adds an l factor) to distinguish uniform vs. a p-planted “needle” in random-order streams, with an initial reduction losing a log n and a second proof removing it. Proof tools are an asymmetric disjointness lower bound via a one-way k-party simulation and a direct information-complexity proof using local needle distributions and a multipass generalization.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:47Needle problem distributions
- 5:47Algorithms and trade-offs
- 6:31Frequency estimation
- 8:19Communication lower bounds
- 13:28Streaming via protocols
- 17:32Asymmetric disjointedness
- 20:51Second proof approach
- 22:21Local needle distribution
- 27:08Information complexity
- 30:39Local complexity intuition
- 36:14Multipass streaming bounds
- 37:27Open questions
- 41:02Small p values
- 42:04Q&A