Expander Flows, Graph Spectra and Graph Separators

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Expander Flows, Graph Spectra and Graph Separators
Speaker:Umesh Vazirani
Affiliation:University of California, Berkeley
Date:Monday, December 3
Time/Room:11:15am - 12:15pm/S-101

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.