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.
-----------------------------------------
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