skip to content

Spectral Sparsification of Graphs

Presented by: 
Nikhil Srivastava University of California, Berkeley
Tuesday 12th July 2016 - 11:00 to 11:30
INI Seminar Room 1
Modern graph algorithms increasingly access and manipulate graphs via their Laplacian operators and other associated “continuous” objects, rather than purely discretely.  An important primitive in this paradigm is spectral sparsification: being able to approximate the Laplacian of a given graph by that of a graph with significantly fewer edges. I will survey some of the key results in this area, drawing on tools from random matrix theory, matrix analysis, and electrical network theory.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons