The main object of this talk is a graph decomposition that partitions a graph in a number of internally-well connected pieces (almost expanders) while ensuring that only a small number of edges connect different pieces. These decomposition arise in fundamental algorithmic problems, including graph sparsification, clustering and the solution of certain systems of linear equations.

This talk will focus on how to produce such a decomposition very fast, i.e. in nearly-linear time, using a novel semidefinite programming approach.

This is joint work with Lorenzo Orecchia.