In the metric Steiner tree problem we are given an $n$‑point metric space $(V,w)$ and a terminal set $T\subseteq V$. The goal is to find the smallest total weight $\mathsf{st}(V,T,w)$ of a tree that spans all terminals and may also use points from $V\setminus T$. We work in the distance‑oracle model: the algorithm knows $V$ and $T$ beforehand and learns the distances $w(u,v)$ only by querying a single entry at a time. The objective is to estimate $\mathsf{st}(V,T,w)$ with as few queries as possible.
A factor‑$2$ approximation can be achieved with nearly linear queries, so the interesting question is the query complexity of algorithms achieving an approximation ratio strictly below $2$. We show that for any fixed $\eta\in(0,1)$, every randomized $(2-\eta)$‑approximation algorithm must make more than $\widetilde{\Omega}(n^{7/5})$ queries, improving the previous $\widetilde{\Omega}(n^{6/5})$ bound. Since the best known upper bound is $\widetilde O(n^{5/3})$ queries, the exponent now lies between $7/5$ and $5/3$, up to logarithmic factors.
Review: This work tightens the known query‑complexity gap for sublinear metric Steiner tree estimation, setting a clearer target for future improvements on both lower and upper bounds.