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.