(Electrical) Flows and Graph Algorithms

31 Oct
Computer Science Colloquium Series
Aleksander Madry, EPFL School of Computer and Communication Sciences
Thursday, October 31, 2013 - 4:00pm
Maxwell Dworkin G125

Graphs are ubiquitous in all modern sciences.  They are conceptually simple while offering the ability to model a surprising variety of complex systems, e.g., the web graph, social networks, road systems, protein interactions, and the brain.  This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner.  This need is even more pressing now that the graphs we are dealing with are often massive and it requires us to expand our algorithmic toolkit to include techniques capable of addressing the emerging challenges.

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.  We illustrate applicability of these ideas by employing them to the maximum flow problem - a problem of key importance in optimization and operations research.  This leads to improvements over some long-standing running time bounds for that problem, as well as brings a new perspective on understanding of the convergence behavior of interior-point methods - a fundamental tool of convex optimization.

Speaker Bio: 

Aleksander Madry is an Assistant Professor of Computer Science in the EPFL School of Computer and Communication Sciences.  His research is centered around algorithmic graph theory, with particular focus on approaching fundamental graph problems with linear algebraic and spectral techniques.

He received his Ph.D. from MIT in 2011.  Before joining EPFL, he spent a year at Microsoft Research, New England.  His work was recognized with a variety of awards, including a number of Best Paper Awards at FOCS/SODA/STOC conferences, as well as ACM Doctoral Dissertation Award Honorable Mention and George M. Sprowls Doctoral Dissertation Award.

Jelani Nelson
Gioia Sweetland