Mathematical Sciences Research Institute

Home » Graph Sparsification


Graph Sparsification September 12, 2011 (04:10PM PDT - 05:00PM PDT)
Location: UC Berkeley, 60 Evans Hall
Speaker(s) Nikhil Srivastava
Description No Description

No Video Uploaded

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.

No Notes/Supplements Uploaded No Video Files Uploaded