MPI-INF Logo
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
English

Date, Time and Location

Wednesday, 23 September 2015
14:00
45 Minutes
E1 4
333 Rotonda
Saarbr├╝cken

Abstract

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.

Contact

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.