Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity
C. S. Karthik, Subhash Khot · Society for Industrial and Applied Mathematics eBooks · 2025
The Gap Exponential Time Hypothesis rules out FPT algorithms providing (nearly) tight inapproximability results for a host of fundamental problems in parameterized complexity. One of the downsides of working under Gap-ETH is that the assumption is not inherently in the parameterized complexity world, and therefore one of the main research directions is to replace Gap-ETH with weaker assumptions.