May 19, 2015, 4:00pm
Jonathan Kelner, Department of Mathematics, MIT.
Bridging the Numerical and the Combinatorial: Emerging Tools, Techniques, and Design Principles for Graph Algorithms
Abstract: Flow and cut problems on graphs are among the most fundamental and extensively studied problems in Operations Research and Optimization, playing a foundational role in both the theory and practice of algorithm design. While the classical algorithms for these problems were largely based on combinatorial approaches, the past several years have witnessed the emergence of a powerful collection of new techniques based on geometry, spectral graph theory, computational linear algebra, randomization, and iterative methods from continuous optimization. These numerical techniques have allowed researchers to provide better provable algorithms for a wide range of graph problems, in some cases breaking algorithmic barriers that had stood for several decades.
The relationship between graph theory and numerical analysis has proven fruitful in the other direction as well. In addition to providing numerical techniques for graph algorithms, it has given rise to new combinatorial techniques for computational linear algebra. In particular, it has led to fast algorithms for Laplacian linear systems, which have broad applications in numerical scientific computing, machine learning, operations research, computer vision, and network analysis, among others.
In this talk, I discuss some of the recurring themes that arise in this confluence of fields. I will apply these to sketch algorithms that run in close to linear time for two basic algorithmic problems: solving Laplacian linear systems and finding approximately maximum flows on undirected graphs.
The talk will be based on joint work with Yin Tat Lee, Aaron Sidford, Lorenzo Orecchia, and Zeyuan Zhu.
Bio: Jonathan Kelner is an Associate Professor of Applied Mathematics in the MIT Department of Mathematics and a member of the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). His research focuses on the application of techniques from pure mathematics to the solution of fundamental problems in algorithms and complexity theory. He was an undergraduate at Harvard University, and he received his Ph.D. in Computer Science from MIT in 2006. Before joining the MIT faculty, he spent a year as a member of the Institute for Advanced Study. He has received a variety of awards for his work, including an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, the Best Paper Awards at STOC 2011, SIGMETRICS 2011, and SODA 2014, the Harold E. Edgerton Faculty Achievement Award, and the MIT School of Science Teaching Prize.