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:

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.