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 very recent work on constructing a linear-sized spectral sparsification in linear time. In particular, I will discuss some interesting connections among graphs, ellipsoids, and balls-into-bins processes. Applications of spectral sparsification in machine learning will be addressed as well.