• German

Main Navigation

He Sun, University of Bristol, OH 14, Room 304

Event Date: March 17, 2016 16:15

Graphs, Ellipsoids, and Balls-into-Bins: A linear-time algorithm for constructing linear-sized spectral sparsification

Spectral sparsification is the procedure of approximating a graph by a sparse graph such that many properties between these two graphs are preserved. Over the past decade, spectral sparsification has become a standard tool in speeding up runtimes of the algorithms for various combinatorial and learning problems.

In this talk I will present our recent work on constructing a linear-sized spectral sparsification in almost-linear time. In particular, I will discuss some interesting connections among graphs, ellipsoids, and balls-into-bins processes.

This is based on joint work with Yin Tat Lee (MIT). Part of the results appeared at FOCS'15.

Newsletter RSS Twitter