Small set expander flows

Small set expander flows - Ali Kemal Sinop

Ali Kemal Sinop
Institute for Advanced Study; Member, School of Mathematics
October 1, 2013

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(logn). 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.