ARC Colloquium: Yin Tat Lee(UW)

*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************

Event Details

Date/Time:
- Monday May 20, 2019 - Tuesday May 21, 2019
  11:00 am - 11:59 am
Location: Klaus 1116 East
Phone:
URL:
Email:
Fee(s):
N/A
Extras:

Contact

No contact information submitted.

Summaries

Summary Sentence: Solving Linear Programs in the Current Matrix Multiplication Time - Klaus 1116 East at 11 am

Full Summary: No summary paragraph submitted.

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