ARC Colloquium: Ramamohan Paturi (UCSD)

*********************************
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 February 13, 2017 - Tuesday February 14, 2017
  11:00 am - 11:59 am
Location: Klaus 1116 East
Phone:
URL: https://www.google.com/maps/place/Klaus+Advanced+Computing+Building/@33.777252,-…
Email:
Fee(s):
N/A
Extras:

Contact

Eric Vigoda

Summaries

Summary Sentence: Genesis of ETH and SETH (Klaus 1116 E at 11 am)

Full Summary: No summary paragraph submitted.

Algorithms & Randomness Center (ARC)

Ramamohan Paturi (UCSD)

Monday, February 13, 2017

Klaus 1116 East - 11:00 am

Title: Genesis of ETH and SETH

Abstract:
Several researchers have found ETH (Exponential Time Hypothesis) and Strong ETH to be useful and proved matching lower bounds for several problems in P as well as NP based on these conjectures. In this talk, I will talk about the technical results that motivated these conjectures. Specifically, I will talk about the following results:

if ETH is false then a number of other NP-complete problems (the class SNP) will also have subexponential time algorithms, and the complexity of k-SAT must keep increasing with k under ETH.

While these results are old, the latter result is relatively less well-known and I hope that it might inspire more work along the lines.

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

Speaker's webpage: http://jacobsschool.ucsd.edu/faculty/faculty_bios/index.sfe?fmp_recid=118

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

Click here to subscribe to the ARC Colloquium mailing list.