STOC'24, a well-known conference in the field of theoretical computer science, recently announced the list of accepted papers. The paper 'Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis' by Yican Sun, a member of PL Lab, was accepted as the best paper. The detail of the paper is presented below.

Title：Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

Authors：Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Abstract: 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 constant fraction of constraints. 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.