即可将网页分享至朋友圈
近日,电子科技大学计算机科学与工程学院(网络空间安全学院)算法与逻辑团队先后在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年获得全国大学生数学竞赛(非数学类)全国第一名等。
编辑:罗莎 / 审核:李果 / 发布:陈伟
即可将网页分享至朋友圈