  This paper presents efficient distributed algorithms for a number of
fundamental problems in the area of graph sparsification:
  We provide the first deterministic distributed algorithm that computes an
ultra-sparse spanner in $\textrm{polylog}(n)$ rounds in weighted graphs.
Concretely, our algorithm outputs a spanning subgraph with only $n+o(n)$ edges
in which the pairwise distances are stretched by a factor of at most $O(\log n
\;\cdot\; 2^{O(\log^* n)})$.
  We provide a $\textrm{polylog}(n)$-round deterministic distributed algorithm
that computes a spanner with stretch $(2k-1)$ and $O(nk + n^{1 + 1/k} \log k)$
edges in unweighted graphs and with $O(n^{1 + 1/k} k)$ edges in weighted
graphs.
  We present the first $\textrm{polylog}(n)$-round randomized distributed
algorithm that computes a sparse connectivity certificate. For an $n$-node
graph $G$, a certificate for connectivity $k$ is a spanning subgraph $H$ that
is $k$-edge-connected if and only if $G$ is $k$-edge-connected, and this
subgraph $H$ is called sparse if it has $O(nk)$ edges. Our algorithm achieves a
sparsity of $(1 + o(1))nk$ edges, which is within a $2(1 + o(1))$ factor of the
best possible.
