Seminar by Nikhil Srivastava
Twice-Ramanujan Sparsifiers
Nikhil Srivastava
Yale University
Date: Friday, September 10th, 2010
Time: 4:00 PM
Venue: CS101.Abstract:
Suppose $G$ is an undirected graph on n vertices. Is there a graph $H$ on the same set of vertices that is 'close' to $G$ and has very few edges? When $G$ is the complete graph then for a certain strong notion of closeness the answer to this question is yes, and the appropriate $H$ are the well-known constant degree expander graphs. We generalize this to all graphs in a certain sense; specifically, we show that for every $\epsilon > 0$, every $G$ contains a weighted subgraph $H$ which has at most $n/\epsilon^2$ edges and satisfies $(1 - \epsilon)^2x^TL_Gx \leq x^TL_Hx \leq (1 + \epsilon)^2x^TL_Gx$, $\forall x \in \mathbb{R}^n$. where $L_G$ and $L_H$ are the Laplacian matrices of $G$ and $H$ respectively. Note that when restricted to $x \in \{0,1\}^n$, this means that the values of all cuts are preserved upto a multiplicative factor of $(1 \pm \epsilon)^2$. The $(1 - \epsilon)^2$ dependence that we achieve is within a factor of two of that achieved by the celebrated Ramanujan graphs. We give a deterministic $O(mn^3/\epsilon^2)$ time algorithm for constructing $H$. Our results about graphs are actually a special case of more general theorems in linear algebra about sparse approximations of decompositions of the identity. Joint work with Josh Batson and Dan Spielman.