Aleksander Madry: From graphs to matrices, and back: bridging the combinatorial and the continuous
Time: Tue 2015-06-02 12.00
Location: Room 4423, Lindstedtsvägen 5, KTH CSC
Participating: Aleksander Madry, MIT
Practicalities
Lunch is served at 12:00 noon (register at this doodle at the latest on Sunday May 31). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
ABSTRACT
Over the last several years there was an emergence of new type of fast algorithms for various fundamental graph problems. A key primitive employed in these algorithms is electrical flow computation, which corresponds to solving a Laplacian linear system.
In this talk, I will discuss how this approach enabled improvement over longstanding bounds for the maximum flow problem. This progress will also illustrate a broader emerging theme of employing optimization methods as an algorithmic bridge between our combinatorial and continuous understanding of graphs.
Additionally, I will briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives --- most notably, interior-point methods.