Pasin Manurangsi - Tutorial on Gap-ETH-based Results

Pasin Manurangsi, Google, presents the "Tutorial on Gap-ETH-based Results" at the DIMACS Workshop on Hardness of approximation in P held at Rutgers University on July 21-23, 2025.

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.

Workshop webpage: http://dimacs.rutgers.edu/events/details?eID=3156

Видео Pasin Manurangsi - Tutorial on Gap-ETH-based Results канала DIMACS CCICADA