2/13/20 | 4:15pm | E51-325
Reception to follow.

Aaron Sidford

Assistant Professor
Stanford

Abstract: Linear programming is one of the most well-studied problems in continuous optimization and a prominent proving ground for new algorithms. In this talk, I will survey recent advances in improving the time complexity of solving linear programs and present recent joint work which shows that linear programs with d variables and n constraints can be solved to high precision in time Otilde(nd + poly(d)), i.e. nearly linear time for tall tall dense linear programs. To achieve this result I will show how to carefully combine a range of algorithmic insights developed over the past decade including, new interior point methods, data structures, and randomized sketches. 

This talk constitutes joint work with Jan van den Brand, Yin Tat Lee, and Zhao Song.

Bio: Aaron Sidford is an assistant professor of Management Science and Engineering and, by courtesy, of Computer Science at Stanford University. He received his PhD from the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where he was advised by Jonathan Kelner. His research interests lie broadly in optimization, the theory of computation, and the design and analysis of algorithms, with an emphasis on work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures. He is the recipient of a NSF CAREER Award, a 2015 ACM Doctoral Dissertation Award honorable mention, and FOCS 2015 and SODA 2014 best paper awards for his work in these areas.