# 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.