Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). Our results improve and generalize the results by Moitra (2009), and Leighton and Moitra (2010). 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 1950s. Using this connection, we prove a lower bound of Omega(sqrt{log k /log log k}) for flow sparsifiers and a super-constant lower bound for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist ilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than ilde Omega(sqrt{log k}) would imply a negative answer to this question.

Questions and Answers

You need to be logged in to be able to post here.