近日，第29届可满足性测试理论与应用国际会议（The 29th International Conference on Theory and Applications of Satisfiability Testing，简称SAT 2026）在葡萄牙里斯本举行。计算机学院算法与逻辑团队发表的题为“New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions”的学术论文，从大会收录论文中脱颖而出，荣获唯一最佳学生论文奖（Best Student Paper Award）。SAT会议是计算机科学理论方向重要国际会议，也是CCF推荐的B类国际会议。今年的SAT会议总共录用46篇论文，评出最佳论文和最佳学生论文各一篇。
该论文由算法与逻辑团队2021级博士生彭俊强（通讯作者）、肖鸣宇教授与来自新加坡国立大学的合作者Sanjay Jain教授、Frank Stephan教授、Haoyun Tang博士生共同完成。
该论文聚焦于奇偶可满足性问题（Parity-SAT，判断给定合取范式是否有奇数个可满足赋值）的高效算法设计与分析。针对一般情形问题及变量出现次数有界的变种问题，论文通过一系列算法设计与结构刻画，提出了多个新型算法，突破了经典运行时间的指数壁垒，取得当前最优奇偶计数算法的运行时间上界，揭示了奇偶性在算法设计层面的优势。本文获得主要算法结果由下表所示。
本届SAT会议组委会在获奖评语中指出，该论文“通过提出新颖的多项式空间算法，打破了长期以来的运行时间界限，从而拓展了奇偶可满足性问题的复杂性研究版图”（for advancing the complexity landscape of parity-SAT by developing novel polynomial-space algorithms that break long-standing running time bounds）。
彭俊强本科期间就进入电子科技大学算法与逻辑团队学习，博士期间继续跟随导师肖鸣宇教授从事SAT相关问题的基础算法研究，目前已在多个SAT相关问题上取得突破，在 Inf. Comput., Theoret. Comput. Sci., SAT, AAAI, IJCAI, WWW等重要国际期刊和会议上发表10余篇论文。本工作是其在国家留学基金委资助下赴新加坡国立大学进行联培期间完成。
计算机（网安）算法与逻辑团队由欧洲科学院院士、新西兰皇家学会院士Bakh Khoussainov教授和算法著名专家肖鸣宇教授共同组建，现有许超教授、Toru Takisaka教授、周毅副教授、郝东副教授等多位骨干成员。团队长期深耕算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等），逻辑，图论与图算法，组合优化，算法工程，机制设计与算法博弈论，形式化方法与认证等理论方向，是我国西部地区理论计算机科学研究方向的一个高地。近年来指导学生在SODA、EC、WINE、CAV、SAT、WWW、AAAI、I&C、JCSS等理论方向顶级会议和期刊上连续发表高水平成果。
论文信息如下（按照理论计算机科学国际学术惯例，论文作者按照姓氏首字母排序）：
标题：New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
作者：Sanjay Jain, Junqiang Peng*, Frank Stephan, Haoyun Tang, Mingyu Xiao
论文链接：https://arxiv.org/abs/2605.14093
