Graph approximation and local clustering, with applications to the solution of diagonally-dominant systems of linear equations

We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms.

The need to quickly partition a graph leads us to the local clustering problem: given a vertex in a massive graph, output a small cluster near that vertex in time proportional to the size of the cluster.

We use all these tools to design nearly-linear time algorithms for solving diagonally-dominant systems of linear equations, and give some applications.

This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Gremban, Miller, Koutis, Emek, Elkin, Andersen, Chung, Lang, Daitch, Srivastava and Batson.