Parameterized Inapproximability Hypothesis under ETH
CoRR(2023)
摘要
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed
parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance,
parameterized by the number of variables, from one where every assignment fails
to satisfy an $\varepsilon$ fraction of constraints for some absolute constant
$\varepsilon > 0$. PIH plays the role of the PCP theorem in parameterized
complexity. However, PIH has only been established under Gap-ETH, a very strong
assumption with an inherent gap.
In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This
is the first proof of PIH from a gap-free assumption. Our proof is
self-contained and elementary. We identify an ETH-hard CSP whose variables take
vector values, and constraints are either linear or of a special parallel
structure. Both kinds of constraints can be checked with constant soundness via
a "parallel PCP of proximity" based on the Walsh-Hadamard code.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要