Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Speaker:He Sun
coming from:University of Bristol
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Wednesday, 23 September 2015
Duration:45 Minutes
Building:E1 4
Room: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.

Name(s):Pavel Kolev
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Pavel Kolev, 09/20/2015 02:07 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Pavel Kolev, 09/20/2015 02:17 PM
  • Pavel Kolev, 09/20/2015 02:07 PM -- Created document.