Reproduce “Near-Optimal Space and Time Cut Sparsification in Turnstile Streams” 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
Honghao Lin, Vahab Mirrokni, David P. Woodruff
The algorithm sparsifies weighted graphs in general-turnstile streams, where edge weights may increase or decrease. It samples by endpoint connectivity and uses unbiased estimates, controlling potentially dependent errors across cuts rather than requiring precise estimates for each edge. For fixed oblivious integer-update streams, it uses tilde O(n/ε²) bits and returns O(n/ε² log² n) edges, preserving every cut within 1±ε with probability at least 1−δ.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.