#### 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.

Done