CSAIL Event Calendar: Previous Series
Expander Flows, Graph Spectra and Graph Separators
Speaker: Umesh Vazirani , UC Berkeley
Relevant URL: http://theory.csail.mit.edu/theory-seminars/calendar.html
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 relationship to metric embeddings as well as the beautiful set of techniques that have been brought to bear upon this problem, including semidefinite programming, spectral methods, and high dimensional geometry.