电子科技大学计算机（网安）学院算法与逻辑团队在计算机理论方向多个顶级国际会议上实现突破

近日，电子科技大学计算机科学与工程学院（网络空间安全学院）算法与逻辑团队先后在LICS、CAV等计算机理论方向的CCF A类会议上发表一系列高水平研究成果，这是我校首次在LICS和CAV这两个CCF A类会议上发表论文。

算法与逻辑团队的Bakh Khoussainov教授为通信作者的论文 Defining algorithmically presented structures in first order logic 被计算机理论方向的国际顶级会议LICS 2024接收。LICS全名为ACM/IEEE Symposium on Logic in Computer Science，是理论计算机科学中逻辑方向最顶级的会议，2024年全球283篇投稿中仅接收了72篇（接收率为25%），其中来自中国作者的论文仅此一篇。

此文主要研究是否可以使用一阶逻辑来正式描述算法表示的结构。这一问题的研究可追溯到50～60年前的古老经典问题，该领域的许多著名专家均尝试过解决这个问题，但是始终没有得到很好的解决方案。Bakh Khoussainov教授潜心在该问题上研究了20余年，最终提出了解决这一问题的积极方法。

算法与逻辑团队的Toru Takisaka教授为第一作者、硕士生王长江为第三作者的论文 Lexicographic Ranking Supermartingales with Lazy Lower Bounds 被计算机理论方向的顶级国际会议CAV 2024接收。CAV全名为International Conference on Computer Aided Verification，是形式化认证中最顶级的国际会议之一，该会议关注从理论到具体应用的各方面研究成果，特别是实用的验证工具以及实现它们所需的算法和技术。

这篇论文主要研究的是Ranking Supermartingale（简称RSM）技术，它是一种用于自动验证概率程序几乎必定终止的重要技术。在该论文中，作者提出了第一种系统分析弱非负性条件下RSM稳健性的技术，基于这一技术，该文设计了一个新的RSM变体，其非负性条件明显弱于现有技术中最先进的RSM变体。实验表明，该项新型RSM合成算法相对现有最先进算法，可行性提高了10.4%。

除以上两篇论文之外，算法与逻辑团队还有四篇论文同时被CCF A类会议IJCAI 2024中的规划、优化、约束满足等传统人工智能基础算法领域接收。IJCAI全名为International Joint Conference on Artificial Intelligence，是人工智能领域历史最长、知名度最高的会议之一，其中传统人工智能基础和理论方向是该会议中难度最大、竞争最激烈的方向之一。四篇被接收的论文具体信息如下：

论文 A Fast Algorithm for MaxSAT Above Half Number of Clauses ，第一作者为博士生彭俊强，第二作者为导师肖鸣宇教授。该文研究了最大可满足性问题（Maximum Satisfiability Problem）以“输入公式的最大可满足子句数与一半子句数之差”这一度量为参数的算法，给出当前最佳的运行时间上界。

论文 A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling ，第一作者为博士生赵景阳，第二作者为导师肖鸣宇教授。该文研究了二分旅行锦标赛问题（Bipartite Traveling Tournament Problem）的调度算法，给出的算法达到了当前最好的理论近似率。

论文 Improved Approximation Algorithms for Capacitated Location Routing ，第一作者为博士生赵景阳，第二作者为导师肖鸣宇教授，第三作者为硕士生汪顺旺。该文研究带容量限制的选址路径规划问题（Capacitated Location Routing），给出的算法改进了原有最佳近似算法。

论文 Exactly Solving Minimum Dominating Set and its Generalization ，第一作者为硕士生熊子良，第二作者为导师肖鸣宇教授。该文针对最小支配集问题及其扩展问题设计了快速的算法，给出了新的约简规则、新的理论下界等，实验效果显示新的算法比原有最佳算法能快上10^5倍。

电子科技大学算法与逻辑团队由欧洲科学院院士、新西兰院士Bakh Khoussainov教授和算法专家肖鸣宇教授共同组建，许超教授、Toru Takisaka教授、周毅副教授、郝东副教授等多位老师参与。该团队致力于基础理论研究，以探索算法难题和解决重要的科学问题为宗旨，激发和培养学生及青年老师对算法和基础理论的兴趣，为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括：算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等），逻辑、图论与图算法，组合优化，算法工程，机制设计与算法博弈论，形式化方法与认证等。团队培养的学生人均发表一篇CCF A类论文，多名学生在程序设计竞赛和数学竞赛中取得优异成绩，如：在ACM程序设计竞赛中10余人进入世界总决赛；在IEEE极限编程竞赛中连续两次获得世界第二名，六次进入世界前十名；两次获得华为软件精英挑战赛全球总决赛冠军；2023年获得全国大学生数学竞赛（非数学类）全国第一名等。