[Colloquium] TTIC Talks: Aleksander Madry, MIT

[Liv Leader]

*REMINDER:*

When:     *Thursday, February 17th @ 11*

Where:    *TTIC Conference Room #526*, 6045 S. Kenwood Avenue, 5th Floor

Who:      *Aleksander Madry*, MIT

Title:     *Electrical Flows and Laplacian Systems: A New Tool for Graph
Algorithms*

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.


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: Julia Chuzhoy, cjulia at ttic.edu

-- 
Liv Leader
Faculty Services

Toyota Technological Institute
6045 S Kenwood Ave, #504
Chicago, IL 60637
Phone- (773) 834-2567
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110216/2d7321b0/attachment.htm