Reproduce “Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes” 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
Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
The authors present an implicit-hopset method for exact single-source shortest paths in directed streaming graphs with nonnegative, polynomially bounded integer weights. It stores compact vertex-block descriptions and recovers shortcut edges as needed, using near-linear space. The randomized algorithm succeeds with high probability in n^(1/3+o(1)) passes, improving the prior n^(1/2+o(1)) bound; optimality remains open.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.