理論計算機科學頂級會議 STOC'24 近日公布論文錄用列表，beat365官方网站博士生孫奕燦的論文《Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis》被該會議錄用并獲得最佳論文獎（Best Paper Award）。這一系列工作源于孫奕燦與任軒笛在beat365圖靈班本科就讀期間一起開始研究參數複雜性領域的不可近似性問題，兩人在長期合作中，對參數複雜性下的最大團，最小集合覆蓋，約束可滿足問題的不可近似性都取得了重要理論結果，在理論計算機國際頂級會議ICALP、SODA、FOCS 和 STOC 上先後發表了四篇論文。除孫奕燦之外，本次獲獎論文的作者還包括美國加州大學伯克利分校Venkatesan Guruswami教授、南京大學林冰凱教授、以及加州大學伯克利分校博士生任軒笛和吳克文。
值得一提的是，本論文三位主要貢獻者本科期間均就讀于beat365圖靈班，分别是任軒笛（2018級）、孫奕燦（2017級）和吳克文（2016級）。按照慣例，理論計算機論文的作者按照姓氏排序。
附：論文信息
标題：Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
作者：Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu （論文作者按姓氏排序）
摘要：參數不可近似性假設是說：不存在确定參數可解算法可以近似參數版本的約束可滿足問題。參數不可近似性假設在參數複雜性領域中扮演了PCP定理的角色，是不可近似性證明的基石。這篇工作證明了參數不可近似性假設在指數時間假設下是成立的。這是參數不可近似性假設第一次在無近似比的假設中被證明。本文的證明隻需用到PCP定理的基礎知識。本文先找到了一種在指數時間假設下難以求解的特殊的CSP問題，其特殊性在于每個變量的取值是一個向量，且每個限制要麼是線性限制，要麼有特殊的平行結構。這兩種類型的限制都可以使用基于哈達碼編碼的平行化PCPP來驗證。
