Computer Science/Discrete Mathematics Seminar I

A graph separator is a set of edges whose deletion partitions the graph into two (or more) pieces. Finding small graph separators is a fundamental combinatorial problem with numerous applications. Interest in it also derives from its theoretical connections to spectral methods, linear/semi-definite programming, high dimensional geometry and measure concentration. In this talk I will speak about approximation algorithms for this problem that are (within poly log factors) as fast as max-flow computations. The analysis of these algorithms is based on a cut-matching game, a new embedding of the graph in R^n called the walk-embedding, and the notion of {\em expander flows}, introduced in [ARV], which constitute an interesting ``certificate'' of a graph's expansion. Based on joint work with Khandekar and Rao, and Orrechia, Schulman and Vishnoi.