Max-Planck-Institut für Informatik
max planck institut
informatik
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)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Wednesday, 23 September 2015
Time:14:00
Duration:45 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:333 Rotonda
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
Name(s):Pavel Kolev
EMail:pkolev@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Pavel Kolev, 09/20/2015 02:07 PMLast modified by: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.