Yican Sun, Peking University

Abstract

The Parameterized Inapproximability Hypothesis (PIH) posits that no fixed-parameter tractable algorithm can distinguish between a satisfiable CSP and one where every assignment violates an $varepsilon$ fraction of constraints, mirroring the foundational role of the PCP theorem in classical complexity. In this talk, I will present a self-contained and elementary proof of PIH, assuming Exponential Time Hypothesis (ETH). The proof proceeds via a reduction from ETH to an ETH-hard, "vector-structured" CSP, where the constraints can be checked for constant soundness using a new, parallel PCP of proximity based on the Walsh–Hadamard code.

After establishing this framework, I will discuss quantitative refinements: specifically, under the same ETH assumption, we show that even sparse k-variable CSPs are hard to approximate within any constant factor in time $n^{k^{1-o(1)}}$. This result yields broad near-optimal inapproximability consequences across parameterized optimization problems.