Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant $\epsilon >0$ such tha…