Seminar

We consider the following type of question: given a finite graph with nonnegative weights on the edges, is there a sparse graph on the same set of vertices (i.e., a graph with very few edges) which preserves the geometry of G?
The answer of course depends on what we mean by preserves and geometry. It turns out that if we are interested in preserving (1) pairwise distances between all pairs of vertices or (2) weights of boundaries of all subsets of vertices, then the answer is always yes in a certain strong sense: every graph on n vertices admits a sparse approximation with O(nlogn) or O(n) edges.

We discuss some of the ideas around the proof of (2), which turns out to be a special case of a more general theorem regarding matrices. The original motivation for this problem was in the design of fast algorithms for solving linear equations, but lately the ideas have found other uses, for instance in metric embeddings and probability.

Joint work with J. Batson and D. Spielman.