Parameterized Inapproximability Hypothesis under ETH
- Xuandi Ren, UC Berkeley
- Time: 2024-06-07 16:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
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 ε 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.
This is a joint work with Venkatesan Guruswami, Bingkai Lin, Yican Sun and Kewen Wu, and is one of the three best papers in STOC'24.
Biography
Xuandi Ren is a second-year Ph.D. student in the theory group of UC Berkeley, where he is advised by Venkatesan Guruswami. He has a broad interest in theoretical computer science, especially in hardness of approximation.