# Small set expander flows

 Computer Science/Discrete Mathematics Seminar II Topic: Small set expander flows Speaker: Ali Kemal Sinop Affiliation: Institute for Advanced Study; Member, School of Mathematics Date: Tuesday, October 1 Time/Room: 10:30am - 12:30pm/S-101 Video Link: https://video.ias.edu/csdm/2013/1001-AliSinop

A common way for lower bounding the expansion of a graph is by looking the second smallest eigenvalue of its Laplacian matrix. Also known as the easy direction of Cheeger's inequality, this bound becomes too weak when the expansion is $o(1)$. In 2004, Arora, Rao and Vazirani proved the existence of "expander flows", which are certificates of graph expansion up to a factor of $O(\sqrt{\log n})$. In this talk, I will describe a generalization of these for small set, "small set expander (SSE) flows", and I will describe an application of such flows for finding near optimal sparse cuts on graphs with certain isoperimetric profiles. This is joint work with Sanjeev Arora and Rong Ge.