Senior Scientist Venkat Guruswami Wins Best Paper Award at STOC 2024

Simons Institute Senior Scientist Venkatesan Guruswami, along with Bingkai Lin, Yican Sun, and Berkeley theory graduate students Xuandi Ren and Kewen Wu, received a best paper award at the 56th ACM Symposium on Theory of Computing (STOC 2024) conference, for their paper, "Parameterized Inapproximability Hypothesis under ETH." STOC is one of the two annual flagship conferences in the theory of computing, along with the IEEE Symposium on Foundations of Computer Science (FOCS). An abstract of the paper is provided below.

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 paper, Guruswami et al. prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. The authors 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.