
CS Colloquium
Thu, Jan 20, 2011 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Aleksander Madry , MIT
Talk Title: Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
Abstract: In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for efficient graph algorithms more pressing than ever. In particular, it lead us to focus on reducing the running time of the algorithms to make them as fast as possible, even if it comes at a cost of reducing the quality of the returned solution. This motivates us to expand our algorithmic toolkit to include techniques capable of addressing this new challenge.
In this talk, I will describe how treating a graph as a network of resistors and relating the combinatorial properties of the graph to the electrical properties of the resulting circuit provides us with a powerful new set of tools for the above pursuit. As an illustration of their applicability, I will use these ideas to develop a new technique for approximating the maximum flow in capacitated, undirected graphs that yields the asymptotically fastestknown algorithm for this problem.
Biography: Aleksander is a PhD candidate in Computer Science at MIT, advised by Michel Goemans and Jonathan Kelner. His research focuses on algorithmic graph theory, i.e. design and analysis of very efficient (approximation) algorithms for fundamental graph problems. He also enjoys investigating topics in combinatorial optimization  especially the ones involving dealing with uncertainty.
Host: Prof. David Kempe
Location: Seaver Science Library (SSL)  150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal