EECS Special Seminar: Aleksander Madry - "From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous"

SHARE:

Event Speaker: 

Aleksander Madry

Event Location: 

32-G449

Event Date/Time: 

Thursday, April 17, 2014 - 4:00pm

Graphs are ubiquitous in all modern sciences, serving as models for a variety of complex systems (e.g., the web graph, social networks, road systems, protein interactions, and the brain). This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate.
In this talk, I will discuss an emerging theme in the design of graph algorithms that approaches problems in the area by connecting combinatorial properties of graphs to linear-algebraic properties of certain associated matrices. In particular, I will describe an application of this approach to the maximum flow problem - a task of key importance in optimization and operations research. The obtained algorithms improve upon the classic results of Even-Tarjan and Hopcroft-Karp.
I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives. Most notably, how it lets us gain an alternative understanding of the convergence behavior of interior-point methods - a fundamental tool in continuous optimization - suggesting an avenue for making progress on certain outstanding questions in that field.
BIO:
Aleksander Madry is an assistant professor in the EPFL School of Computer and Communication Sciences. His research centers on tackling fundamental algorithmic problems that are motivated by real-world optimization. Most of his work is concerned with developing new ideas and tools for algorithmic graph theory, with a particular focus on approaching central questions in that area with a mix of combinatorial and linear-algebraic techniques. He is also interested in understanding uncertainty in the context of optimization – how to model it, and how to cope with its presence.
Aleksander received his PhD from MIT in 2011 and, prior to joining EPFL, spent a year as a postdoctoral researcher at Microsoft Research New England. His work was recognized with a variety of awards, including the ACM Doctoral Dissertation Award Honorable Mention, the George M. Sprowls Doctoral Dissertation Award, and a number of best paper awards at FOCS/SODA/STOC conferences.