Pasin Manurangsi, Google

Abstract

Exponential time hypothesis (ETH)--which postulates that no sub-exponential time algorithm can solve 3-SAT--is one of the main assumptions in proving tight running time lower bounds for exponential-time and parameterized algorithms. Gap-ETH is an extension of ETH which roughly asserts that even approximating Max-3-SAT requires exponential time. This stronger assumption helps facilitate the proofs in hardness of approximation results for parameterized algorithms. While some of these results have now been proved under the weaker ETH, others remain known only under Gap-ETH. This talk will discuss Gap-ETH hardness results, especially those that are not yet known under ETH. Finally, we will discuss some problems whose (tight) hardness of approximation results are not even known under Gap-ETH.