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.
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.