Speaker:

Bingkai Lin (Nanjing University)

Time:

• 16:20-17:20 Beijing Time
• Dec 2, 2024 (Monday)

Venue:

518, Research Building 4

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 $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 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.

Speaker Bio:

林冰凯，南京大学计算机学院教授，博士生导师。博士毕业于日本东京大学，硕士及本科毕业于上海交通大学ACM试点班。研究领域是理论计算机科学，具体领域是参数复杂性(Parameterized Complexity) 及近似算法 (Approximation Algorithms)。主要成果包括独自解决了参数复杂性领域基础性难题——k-BICLIQUE问题的参数复杂性;在图嵌入问题参数复杂性的二分猜想这一长达十多年的公开问题上取得重要进展；对经典NP-难优化问题集合覆盖问题取得首个以及当前最好的参数算法不可近似比；证明了指数时间假设蕴含参数不可近似假设，推动了参数PCP理论的发展。成果获得理论计算机国际一流会议STOC 2024与计算机科学图论领域重要国际会议WG 2017最佳论文奖。两篇单独作者论文分别获国际算法会议SODA 2015最佳论文奖和最佳学生论文奖以及欧洲理论计算机重要会议ICALP 2019最佳论文奖。