CATS-Feb-27-2015
From Theory
Title[edit]
Spectral Sparsification
Speaker[edit]
Karthik Abhinav Sankararaman
Abstract[edit]
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.
