Nevanlinna Prize Talk: Laplacian Gems

Dan Spielman

Abstract

I will explain some of the most interesting applications of solving linear equations in Laplacian matrices as well as some of the most interesting ideas that have been used in algorithms that solve these equations. The main applications will come from machine learning and optimization. The algorithmic ideas I discuss will include local clustering, sparsification, low-stretch spanning trees, and an under-appreciated technique of Lovasz and Simonovits for bounding the convergence rate of Markov chains.