Title: Graph Sparsification
Speaker: Nikhil Srivastava (Microsoft Research India)

A spectral sparsifier for a given graph G is a sparser graph H on the same set
of vertices such that the Laplacians L_G and L_H have a small relative
condition number and are therefore good preconditioners of each other.
Originating in the work of Spielman and Teng, this notion has been a key
ingredient in the construction of nearly-linear time Laplacian solvers. We
describe a simple sampling scheme which gives sparsifiers of size O(n\log n)
for every graph. The analysis of the scheme reduces the original
graph-theoretic question to a purely linear-algebraic question, which is then
solved by matrix Chernoff bounds. The sampling rule has a natural
interpretation in terms of electrical circuits and can be implemented in nearly
linear time using random projections