Fall 2017

Solving Linear Programs in the Current Matrix Multiplication Time

Wednesday, December 12th, 2018 1:45 pm2:30 pm

Add to Calendar


YinTat Lee (University of Washington)

In this talk, I will explain how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of solving linear programs since linear systems is a special case of linear programs and solving linear systems require time n^omega currently. Joint work with Michael Cohen and Zhao Song.