  We study vertex cut and flow sparsifiers that were recently introduced by
Moitra, and Leighton and Moitra. We improve and generalize their results. We
give a new polynomial-time algorithm for constructing O(log k / log log k) cut
and flow sparsifiers, matching the best existential upper bound on the quality
of a sparsifier, and improving the previous algorithmic upper bound of O(log^2
k / log log k). We show that flow sparsifiers can be obtained from linear
operators approximating minimum metric extensions. We introduce the notion of
(linear) metric extension operators, prove that they exist, and give an exact
polynomial-time algorithm for finding optimal operators.
  We then establish a direct connection between flow and cut sparsifiers and
Lipschitz extendability of maps in Banach spaces, a notion studied in
functional analysis since 1930s. Using this connection, we prove a lower bound
of Omega(sqrt{log k/log log k}) for flow sparsifiers and a lower bound of
Omega(sqrt{log k}/log log k) for cut sparsifiers. We show that if a certain
open question posed by Ball in 1992 has a positive answer, then there exist
\tilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on
cut sparsifiers better than \tilde Omega(sqrt{log k}) would imply a negative
answer to this question.
