[Discrete-math-seminar] Fwd: [Theory] TTIC Talks: Aleksander Madry, MIT

Robert Ellis rellis at math.iit.edu
Wed Feb 16 15:13:47 CST 2011

The following talk at TTI tomorrow at 11am may be of interest, especially in
light of last week's discussion of approximation algorithms.

-Robert Ellis

---------- Forwarded message ----------
From: Liv Leader <lleader at ttic.edu>
Date: Wed, Feb 16, 2011 at 12:46 PM
Subject: [Theory] TTIC Talks: Aleksander Madry, MIT
To: TTIC Talks <talks at ttic.edu>, theory at cs.uchicago.edu,
colloquium at cs.uchicago.edu


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

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

Theory mailing list
Theory at mailman.cs.uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://math.iit.edu/pipermail/discrete-math-seminar/attachments/20110216/42cb7a8b/attachment.html 

More information about the Discrete-math-seminar mailing list