Continuing on the theme of sparsification, in this talk I will present a neat algorithm due to Spielman and Srivatsava on spectral sparsification. The aim of the talk is to introduce some notions from spectral graph theory, look at how a different perspective of graph as a physical object such as electrical network helps in realising many properties and also some interesting mathematical tools. This algorithm is from the following paper

 

"Graph Sparsification by Effective Resistances", Daniel A Spielman, Nikhil Srivatsava [STOC '08] (http://arxiv.org/pdf/0803.0929.pdf)

 

This talk might be useful for a broader range of audience, outside theory as well. So, all are invited to attend.