event

ARC Colloquium: Ramamohan Paturi (UCSD)

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.

Media

No media selected

Summary

Details

Monday
Feb 13 2017
11:00am - 12:00pm

Contact: Eric Vigoda

URL: https://www.google.com/maps/place/Klaus+Advanced+Computing+Building/@33.777252,-84.396185,17z/data=!3m1!4b1!4m2!3m1!1s0x87b781ec0ab42ea5:0x16eec927f37b40ec

In campus calendar: No

Sidebar Content

No sidebar content

Groups

Status

  • Workflow Status:Published
  • Created By:Dani Denton
  • Created:08/08/2016
  • Modified By:Fletcher Moore
  • Modified:04/13/2017

Related Links

Categories

Keywords

Target Audience