ARC Colloquium: Yin Tat Lee(UW)

Algorithms & Randomness Center (ARC)

Yin Tat Lee (UW)

Monday, May 20, 2019

Klaus 1116E - 11:00 am

 

Title:  Solving Linear Programs in the Current Matrix Multiplication Time

Abstract:  We show 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 B. Cohen and Zhao Song.

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu

 

Event Details

Date/Time:

  • Monday, May 20, 2019
    12:00 pm - 1:00 pm