From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous

Speaker: Aleksander Madry , École Polytechnique Fédérale de Lausanne (EPFL)

Date: Thursday, April 17, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host:

Contact: Francis Doughty, francisd@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: Aleksander Madry: From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous

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.

Research Areas:

Impact Areas:

See other events that are part of the CS Special Seminar Series 2014.

Created by Francis Doughty at Thursday, February 20, 2014 at 2:02 PM.