Reproduce “Optimal (Randomized) Compact Routing Schemes” 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
Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty
The authors present a labeled routing scheme for undirected graphs that uses average local storage of O(n^{1/k}) words and guarantees expected route length at most 2k−1 times shortest-path distance for each fixed source–destination pair. The source randomizes its pivot choice, while preprocessing fixes tables and labels. Under the Erdős girth conjecture, this stretch is optimal up to polylogarithmic storage factors.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.