Large 00020

Spectral Sparsification of Graphs and Approximations of Matrices

Daniel Spielman

Recorded 11 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute

Abstract

We will review the fundamental algorithms for spectrally approximating matrices, with an emphasis on the Laplacian matrices of graphs. We then survey recent improvements in algorithms for sparsifying Laplacian matrices.

We devote the last part of the talk to making connections and stating open problems. In particular, we observe that one can sparsify Maximum Cut problems and Unique Games, as well as the linear equations that occur in many optimization algorithms.

Watched 16105 times.

 Watch