Reproduce “A Better Lower Bound for Sublinear Metric Steiner Tree” 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

Sepideh Mahabadi, Jakub Tarnawski, Ali Vakilian

The authors prove that estimating metric Steiner tree cost from distance queries below factor 2 requires many queries. They construct hidden instances with different optimum costs but locally similar query answers, so distinguishing them requires coordinated observations in a randomly hidden block. For every fixed eta in (0,1), estimation within factor 2−eta needs Ω_eta(n^(7/5)/log n) queries with linearly many terminals; this remains below the known O-tilde(n^(5/3)) upper bound.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.