Faster algorithms for fundamental convex problems and their applications in combinatorial optimization

Convex optimization has been studied extensively and is a prominent tool in various areas such as combinatorial optimization, data analysis, operations research, and scientific computing.  Each field has developed specialized tools including data structures, sampling methods, and dimension reduction. In the past several years, I have been combining and improving the optimization techniques from different fields to design faster optimization algorithms. 

 In this talk, I will discuss my work in this direction and illustrate it through my results on linear programming and general convex optimization. In particular, I will present a new algorithm for solving linear programs, which gives the first improvement to the running time for linear programming in 25 years. Then, I will present the first nearly cubic time algorithm for solving general convex optimization problems. Furthermore, I will discuss how these two results can be used to improve the running time of many classical combinatorial problems such as maximum flow and submodular function minimization.

 This talk will assume no prior knowledge of optimization.

Yin Tat Lee is a Ph.D. candidate in the department of mathematics at the Massachusetts Institute of Technology. He is interested in designing faster algorithms, particularly for problems in optimization. Since he began his Ph.D. in 2012, he has combined ideas from continuous and discrete mathematics to substantially advance the state-of-the-art for solving many fundamental problems in computer science, such as linear programming, maximum flow, and submodular function minimization. He has received a variety of awards, including the Best Student Paper Award at FOCS 2015, Best Paper Award at SODA 2014, Best Paper Award and Best Student Paper Award at FOCS 2014, and Notable Article in Computing in 2014 by Computing Reviews.