Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
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 fastest-known algorithm for this problem.
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.