Nisheeth Vishnoi
(Microsoft Research India and Adjunct Faculty, CSE, IITK)
Date: Wednesday, January 2nd, 2013
Time: 6 PM
Venue: CS101.
The ability to solve a system of linear equations lies at the heart of areas such as optimization, scientific computing and computer science and, traditionally, has been a central topic of research in the area of numerical linear algebra. An important class of instances that often arises in practice, e.g., in areas such as scientific computing and computer vision, has the form Lx=b where L is the Laplacian of an undirected graph G with n vertices and m edges with m (typically) much smaller than n^2. After more than 30 years of sustained research, combining tools from graph partitioning, random walks and low-stretch spanning trees with numerical methods based on Gaussian elimination and the conjugate gradient, we now have a Laplacian solver that runs in O(m log n) time. For instance, this result allows one to compute currents and voltages in a resistive electrical network in time roughly proportional to the number of resistances.
Surprisingly, and perhaps not its original intention, this result is in the process of revolutionizing the theory of fast algorithms for fundamental graph problems; giving back to an area that empowered this work in the first place. In this talk I will give an overview of this emerging paradigm of employing Laplacian solvers to design novel fast algorithms for graph problems. Time permitting, I will also talk about how to solve Laplacian systems quickly.