Aleksander Madry Colloquium, Thursday, 3:30pm
David Kempe
our first theory hiring talk this semester will be Aleksander Madry
from MIT, this coming Thursday (01/20), at 3:30pm in SSL 150.
All the important information is below.
This should be a very exciting talk about the first significant
progress on Maximum Flow in a long time.
Looking forward to seeing many of you there.
Title: Electrical Flows and Laplacian Systems: A New Tool for Graph
Algorithms
Speaker: Aleksander Madry, MIT (Faculty Candidate)
Time: 3:30 PM - 5 PM
Location: SSL 150
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 fastest-known algorithm for this
problem.
Bio:
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.
--
David Kempe <dke...@usc.edu>