科研学术

　　近日，电子科技大学计算机科学与工程学院（网络空间安全学院）算法与逻辑团队先后在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年获得全国大学生数学竞赛（非数学类）全国第一名等。