Konstantin Makarychev

Metric Extension Operators, Vertex Sparsifiers and Lipschitz
Extendability

ABSTRACT:	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 known 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 1950s.
Using this connection, we obtain a lower bound of
Omega(sqrt{log k / loglog k}) for flow sparsifiers and a lower
bound of Omega(sqrt{log k}loglog k for cut sparsifiers. We show
that if a certain open question posed by Ball in 1992 has a
positive answer, then there exist ~O(sqrt{log k}) cut
sparsifiers. On the other hand, any lower bound on cut
sparsifiers better than Omega(sqrt{log k}) would imply a
negative answer to this question.

This is a joint work with Yury Makarychev (Toyota Technological
Institute at Chicago).


BIO: Konstantin Makarychev is a research staff member at IBM
Research. He graduated from Princeton University in 2007.