Genesis of ETH and SETH - Ramamohan Paturi

From Katie Gentilello February 23rd, 2017

12 plays 0 comments

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.
https://mediaspace.gatech.edu/media/paturi/1_gy1j0fjr

Tags: algorithms and randomness centerarc colloquiumgeorgia techrecorded by gtlibraryspring 2017

name: Ramamohan Paturi
Date: February 13th, 2017
Appears In: Open Scholarship

Comments
Related Media

Loading…

Genesis of ETH and SETH - Ramamohan Paturi

Related Media