Speaker:

Venkatesan Guruswami (University of California, Berkeley)

Time:

• 9:00-10:00 Beijing Time
• February 26, 2025 (Wednesday)

Venue:

518, Research Building 4

Abstract:

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable instance of a constraint satisfaction problem (CSP) parameterized by the number of variables, from one where every assignment fails to satisfy 1% of the constraints. PIH plays the role of the PCP theorem in parameterized complexity, with many downstream inapproximability consequences.

This talk will introduce the context and statement of the PIH, and then sketch the ideas behind a recent proof showing that the well-known Exponential Time Hypothesis (ETH) implies the PIH. The approach involves two broad steps. The first identifies a highly structured ETH-hard CSP whose variables take vector values, and whose constraints are either parallel or linear. Both kinds of constraints are then checked with constant soundness via a “parallel PCP of proximity” based on the Hadamard code. We will briefly mention follow-up improvements that employ Reed-Muller code based PCPs to even get near-optimal runtime lower bounds, eg. showing that constant factor approximations to k-clique on n-vertex graphs requires n^{k^{1-o(1)}} time under ETH.

Based on joint works with Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu.

Speaker Bio:

Venkatesan Guruswami is a Professor of Computer Science and Mathematics at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor’s degree from the Indian Institute of Technology, Madras, and his Ph.D. from MIT.

Venkat’s research interests include coding theory, constraint satisfaction, approximate optimization, and computational complexity. He is the Editor-in-Chief of JACM, and was previously president of the Computational Complexity Foundation. Venkat is a recipient of the Presburger Award, a Simons Investigator award, Guggenheim, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and a distinguished alumnus award from IIT Madras.  He is a fellow of the ACM, IEEE, and AMS.