Title: Solving Laplacian Linear Equations: Theory and Practice Speaker: Yiannis Koutis (University of Puerto) Co-authors: Alex Levin, Gary Miller, Richard Peng Abstract: Laplacian linear system solvers are central in what has been described as an "incipient revolution in the theory of graph algorithms". Indeed, fast Laplacian solvers are a key subroutine of the fastest known approximation algorithms for several problems, including image de-noising and the max-flow problem. We survey the graph theory concepts and approaches behind the asymptotically fastest known Laplacian solver and `Combinatorial Multigrid' (CMG), a state-of-the-art implementation for sparse systems. We also discuss our recent efforts --partly motivated by the desire to extend the usability of CMG-- to design practical spectral sparsification algorithms. A by-product of this work is an improved, linear time solver for slight dense Laplacian systems.