  We study the query complexity of the metric Steiner Tree problem, where we
are given an $n \times n$ metric on a set $V$ of vertices along with a set $T
\subseteq V$ of $k$ terminals, and the goal is to find a tree of minimum cost
that contains all terminals in $T$. The query complexity for the related
minimum spanning tree (MST) problem is well-understood: for any fixed
$\varepsilon > 0$, one can estimate the MST cost to within a
$(1+\varepsilon)$-factor using only $\tilde{O}(n)$ queries, and this is known
to be tight. This implies that a $(2 + \varepsilon)$-approximate estimate of
Steiner Tree cost can be obtained with $\tilde{O}(k)$ queries by simply
applying the MST cost estimation algorithm on the metric induced by the
terminals.
  Our first result shows that any (randomized) algorithm that estimates the
Steiner Tree cost to within a $(5/3 - \varepsilon)$-factor requires
$\Omega(n^2)$ queries, even if $k$ is a constant. This lower bound is in sharp
contrast to an upper bound of $O(nk)$ queries for computing a
$(5/3)$-approximate Steiner Tree, which follows from previous work by Du and
Zelikovsky.
  Our second main result, and the main technical contribution of this work, is
a sublinear query algorithm for estimating the Steiner Tree cost to within a
strictly better-than-$2$ factor, with query complexity $\tilde{O}(n^{12/7} +
n^{6/7}\cdot k)=\tilde{O}(n^{13/7})=o(n^2)$. We complement this result by
showing an $\tilde{\Omega}(n + k^{6/5})$ query lower bound for any algorithm
that estimates Steiner Tree cost to a strictly better than $2$ factor. Thus
$\tilde{\Omega}(n^{6/5})$ queries are needed to just beat $2$-approximation
when $k = \Omega(n)$; a sharp contrast to MST cost estimation where a
$(1+o(1))$-approximate estimate of cost is achievable with only $\tilde{O}(n)$
queries.
