Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity
Karthik C. S., Subhash Khot
2025Year
1Citations
Abstract
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.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Related papers
- Parameterized Inapproximability Hypothesis under Exponential Time HypothesisVenkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun et al.STOC 2024 · 6 citations
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)Pasin ManurangsiSODA 2020 · 30 citations
- The Primal Pathwidth SETHMichael LampisSODA 2025 · 1 citation
- Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETHVenkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun et al.STOC 2025 · 3 citations
- Treewidth Inapproximability and Tight ETH Lower BoundÉdouard BonnetSTOC 2025 · 1 citation
