理论计算机科学顶级会议 STOC'24 近日公布论文录用列表，北京大学计算机学院博士生孙奕灿的论文《Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis》被该会议录用并获得最佳论文奖（Best Paper Award）。这一系列工作源于孙奕灿与任轩笛在北京大学图灵班本科就读期间一起开始研究参数复杂性领域的不可近似性问题，两人在长期合作中，对参数复杂性下的最大团，最小集合覆盖，约束可满足问题的不可近似性都取得了重要理论结果，在理论计算机国际顶级会议ICALP、SODA、FOCS 和 STOC 上先后发表了四篇论文。除孙奕灿之外，本次获奖论文的作者还包括美国加州大学伯克利分校Venkatesan Guruswami教授、南京大学林冰凯教授、以及加州大学伯克利分校博士生任轩笛和吴克文。

值得一提的是，本论文三位主要贡献者本科期间均就读于北京大学图灵班，分别是任轩笛（2018级）、孙奕灿（2017级）和吴克文（2016级）。按照惯例，理论计算机论文的作者按照姓氏排序。

附：论文信息

标题：Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

作者：Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu （论文作者按姓氏排序）

摘要：参数不可近似性假设是说：不存在确定参数可解算法可以近似参数版本的约束可满足问题。参数不可近似性假设在参数复杂性领域中扮演了PCP定理的角色，是不可近似性证明的基石。这篇工作证明了参数不可近似性假设在指数时间假设下是成立的。这是参数不可近似性假设第一次在无近似比的假设中被证明。本文的证明只需用到PCP定理的基础知识。本文先找到了一种在指数时间假设下难以求解的特殊的CSP问题，其特殊性在于每个变量的取值是一个向量，且每个限制要么是线性限制，要么有特殊的平行结构。这两种类型的限制都可以使用基于哈达码编码的平行化PCPP来验证。