Almost-Linear-Time Algorithms for Fundamental Graph Problems: A New Framework and Its Applications: Lorenzo Orecchia, MIT (CS Colloquium)

Starts:
11:00 am on Friday, March 7, 2014
Ends:
12:15 pm on Friday, March 7, 2014
Location:
Hariri Institute
Abstract: Classical algorithms for many important graph primitives were designed at a time when the notion of efficiency was polynomial time in the input size. However, many of todays applications involve massive graphs, consisting of millions and even billions of nodes, and require algorithms whose running time is linear or almost-linear, i.e., linear up to lower-order terms, in the size of the input. Despite sustained work in this area since the birth of Theoretical Computer Science, state-of-the-art algorithms still fail to achieve an almost-linear running time for many crucial problems. In this talk, I will showcase some of my contributions to overcoming this longstanding barrier by describing novel almost-linear-time algorithms for a number of fundamental graph problems. In particular, I will present: i) the first almost-linear-time algorithms for maximum-flow problems on undirected graphs, a foundational computational challenge in Combinatorial Optimization; ii) a very simple method for solving Laplacian systems of linear equations that yields the fastest known algorithm for this ubiquitous problem in Scientific Computing and Numerical Analysis; iii) the first almost-linear-time algorithm with provable high-quality guarantees for graph clustering, i.e. the problem of partitioning a graph into well-connected components without cutting too many edges. This problems and variations of it play important roles in Algorithmic Graph Theory and Machine Learning. Furthermore, I will demonstrate how each of these methods is an instantiation of a wider design framework, which combines techniques from discrete and continuous optimization, and allows us to construct conceptually simple, yet computationally powerful algorithms. Bio: Lorenzo Orecchia is an Applied Mathematics Instructor at the Massachusetts Institute of Technology. Lorenzo obtained his Ph.D. in Theoretical Computer Science at UC Berkeley under the supervision of Satish Rao in 2011. He is a recipient of the Best Paper Award at the 2014 Symposium on Discrete Algorithms for his work on fast algorithms for the maximum-flow problem.