理论计算机科学顶级会议 STOC'24 近日公布论文录用名单，程序设计语言研究室孙奕灿同学的论文《Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis》被该会议录用并获得最佳论文奖（Best Paper Award）。

标题：Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

作者：Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

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