  We address the fundamental network design problem of constructing approximate
minimum spanners. Our contributions are for the distributed setting, providing
both algorithmic and hardness results.
  Our main hardness result shows that an $\alpha$-approximation for the minimum
directed $k$-spanner problem for $k \geq 5$ requires $\Omega(n
/\sqrt{\alpha}\log{n})$ rounds using deterministic algorithms or
$\Omega(\sqrt{n }/\sqrt{\alpha}\log{n})$ rounds using randomized ones, in the
CONGEST model of distributed computing. Combined with the constant-round
$O(n^{\epsilon})$-approximation algorithm in the LOCAL model of [Barenboim,
Elkin and Gavoille, 2016], as well as a polylog-round
$(1+\epsilon)$-approximation algorithm in the LOCAL model that we show here,
our lower bounds for the CONGEST model imply a strict separation between the
LOCAL and CONGEST models. Notably, to the best of our knowledge, this is the
first separation between these models for a local approximation problem.
  Similarly, a separation between the directed and undirected cases is implied.
We also prove a nearly-linear lower bound for the minimum weighted $k$-spanner
problem for $k \geq 4$, and we show lower bounds for the weighted 2-spanner
problem.
  On the algorithmic side, apart from the aforementioned
$(1+\epsilon)$-approximation algorithm for minimum $k$-spanners, our main
contribution is a new distributed construction of minimum 2-spanners that uses
only polynomial local computations. Our algorithm has a guaranteed
approximation ratio of $O(\log(m/n))$ for a graph with $n$ vertices and $m$
edges, which matches the best known ratio for polynomial time sequential
algorithms [Kortsarz and Peleg, 1994], and is tight if we restrict ourselves to
polynomial local computations. Our approach allows us to extend our algorithm
to work also for the directed, weighted, and client-server variants of the
problem.
