Thursday, April 18, 2019 4:00 pm
-
4:00 pm
EDT (GMT -04:00)
Title: Graph Sparsification by Effective Resistances
| Speaker: | Akshay Ramachandran |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
We will discuss an application of the matrix concentration inequalities of Tropp to spectral sparsification of graphs. The result presented in "Graph Sparsification by Effective Resistances" (Spielman, Srivastava 09) uses independent sampling to produce a near-linear size sparsifier. The analysis will relate spectral graph parameters, like effective resistance, to relevant convergence parameters of matrix concentration.