Spectral Graph Sparsification and Fast Laplacian Solvers: Yiannis Koutis, Brown (Theory Seminar)
- Starts: 2:00 am on Monday, May 5, 2014
- Ends: 4:00 am on Monday, May 5, 2014
Abstract: Algorithms for solving linear systems involving graph Laplacians are now capable of handling graphs with millions of edges. They have consequently become an important algorithmic primitive with applications in diverse areas. Central to the design of fast solvers is the problem of spectral graph sparsification. We describe an extremely simple sparsification algorithm, the first to admit an implementation in the distributed model. The simplicity of the algorithm provides an opportunity for a review of the interplay between combinatorial algorithms and algebra that forms the basis of most recently discovered fast Laplacian solvers. Bio: Ioannis Koutis is an assistant professor in the Computer Science Department at the University of Puerto Rico, Rio Piedras. He holds a PhD in Computer Science from Carnegie Mellon University, and a Diploma in Computer Engineering and Informatics from the University of Patras, Greece. His research interests include algorithmic applications of spectral graph theory, numerical computations with provable properties and algebraic algorithms for parameterized and exact problems.
- MCS 148