Electrical Flows and Fast Graph Algorithms

Tuesday, March 17, 2015 - 2:50pm - 3:30pm
Klaus 2443
Aleksander Madry (Massachusetts Institute of Technology)
Over the last several years, there was an emergence of new type of fast algorithms for various fundamental graph problems. A key primitive employed in these algorithms is electrical flow computation, which corresponds to solving a Laplacian linear system.

In this talk, I will briefly discuss these developments as well as the role that electrical flow computations play in them. In particular, I will present in more detail a recent progress on fast generation of random spanning trees.