Personal tools
You are here: Home Events Title: Graphs, Ellipsoids, and Balls-into-Bins: A linear-time algorithm for constructing linear-sized spectral sparsifiers

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

— filed under:

Speaker: He Sun

What
  • Lab Lunch
When Nov 28, 2017
from 01:00 PM to 02:00 PM
Add event to calendar vCal
iCal

 

Abstract:

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 sparsifiers 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.

The talk is based on the recent publications appearing in FOCS'15, NIPS?16, and STOC?17.

Document Actions