Reproduce “Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang
The authors characterize optimal space for one-report unrestricted dynamic streams that insert and delete edges while reporting a spanning forest. Their method compactly encodes neighbor information and schedules recovery of edges crossing component boundaries. For failure probability δ, its space matches a lower bound for all algorithms; at δ=2⁻ᵛ/ˡᵒᵍ²ᵛ, memory is Θ(v²(log log v)²/log² v), below the prior O(v²) guarantee.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.