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
Note: We use this to send email in the morning.
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 14:17
Pavel Kolev, 09/20/2015 14:07 -- Created document.
Pavel Kolev, 09/20/2015 14:07 -- Created document.