BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Monday Seminar : "Electrical Flows and Laplacian Systems: A New
  Tool for Graph Algorithms"
DTSTART:20110418T161500
DTSTAMP:20260916T084546Z
UID:70bb36cac018913558568a53ce20fcb09660b890b9f9c39495f75cf8
CATEGORIES:Conferences - Seminars
DESCRIPTION:Dr. Aleksander Madry\, Massachusetts Institute of Technology -
  IC Faculty Candidate\nAbstract: In recent years\, the emergence of massiv
 e computing tasks that arise in context of web applications and networks h
 as made the need for efficient graph algorithms more pressing than ever. I
 n particular\, it lead us to focus on reducing the running time of the alg
 orithms to make them as fast as possible\, even if it comes at a cost of r
 educing the quality of the returned solution. This motivates us to expand 
 our algorithmic toolkit to include techniques capable of addressing this n
 ew challenge. In this talk\, I will describe how treating a graph as a net
 work of resistors and relating the combinatorial properties of the graph t
 o the electrical properties of the resulting circuit provides us with a po
 werful 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 app
 roximating the maximum flow in capacitated\, undirected graphs that yields
  the asymptotically fastest-known algorithm for this problem. Bio: Aleksan
 der is a PhD candidate in Computer Science at MIT\, advised by Michel Goem
 ans and Jonathan Kelner. His research focuses on algorithmic graph theory\
 , i.e. design and analysis of very efficient (approximation) algorithms fo
 r fundamental graph problems. He also enjoys investigating topics in combi
 natorial optimization - especially the ones involving dealing with uncerta
 inty.
LOCATION:INM 202
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR