Campus Event Calendar

Event Entry

What and Who

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

He Sun
University of Bristol
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Wednesday, 23 September 2015
45 Minutes
E1 4
333 Rotonda


Spectral sparsification is the procedure of approximating a graph by a sparse graph such that many spectral properties between two graphs are preserved. Since both storing and processing large-scale graphs are expensive, spectral sparsification has become one of the most fundamental and powerful components in designing fast graph algorithms, and has wide applications in numerical linear algebra, streaming algorithms, and various pure mathematical problems.

In this talk I will present our recent work on constructing a linear-sized spectral sparsification in almost-linear time. Our algorithm is based on a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.

This is is joint work with Yin Tat Lee, and the work is to appear in FOCS 2015.


Pavel Kolev
--email hidden
passcode not visible
logged in users only

Pavel Kolev, 09/20/2015 02:17 PM
Pavel Kolev, 09/20/2015 02:07 PM -- Created document.