Alladi Ramakrishnan Hall

Parameterized Inapproximability Hypothesis under ETH

Venkatesan Guruswami

UC Berkeley

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 fraction of
constraints for some absolute constant 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.