CS Peer Talk | Parameterized Inapproximability Hypothesis...

报告人：Xuandi Ren, UC Berkeley

时间：6月7日（星期五）4:00pm

地点：静园五院204

Host：黄致焕，图灵班2017级

Parameterized Inapproximability Hypothesis under ETH

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.

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.

北京大学图灵班科研活动委员会