Reproduce “Connectivity in a New Bounded-Space Dynamic Model” 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
Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams
The authors formalize maintaining whether two fixed vertices are connected in a read-only graph with limited writable workspace. Their monitor can reread the graph, while all persistent and temporary memory counts toward its budget. In the list model, incremental worst-case update time is tight at Õ(n²/S²); amortized time is Õ(n/S), with a lower bound of Õ(√(n/S)), leaving a gap.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.