Title:
Solving Linear Programs in the Current Matrix Multiplication Time
Solving Linear Programs in the Current Matrix Multiplication Time
Author(s)
Lee, Yin Tat
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
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.
Sponsor
Date Issued
2019-05-20
Extent
59:18 minutes
Resource Type
Moving Image
Resource Subtype
Lecture