Spectral Sparsification of Graphs and Approximations of Matrices
Recorded 11 June 2012 in Lausanne, Vaud, Switzerland
Event: SuRI - I&C - Summer Research Institute
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 1109 times.Watch