近日，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队在理论计算机科学领域CCF A类顶级期刊《Information and Computation》上连续发表三篇高水平研究论文，充分展现了团队在该领域的突出科研实力与国际学术影响力。 《Information and Computation》自1957年创刊以来，始终秉持严格的学术标准与高要求的录用政策，是CCF推荐A类期刊中理论计算机科学方向的权威刊物。该刊每年发文量通常不超过100篇（除两年特例外），发表难度极高。据文献[黄铁军，我国计算机科学国际期刊论文状况，中国计算机学会通讯，11(8)2015]统计，该期刊是国内学者发表数量最少的CCF A类期刊之一。此次算法与逻辑团队连续三篇论文被该刊录用，标志着我校在理论计算机科学前沿研究领域取得重要突破。 第一篇论文题为“Exponential time algorithms for deciding regular games”（判定正则博弈的指数时间算法），第一作者为梁子辉博士，指导老师Bakh教授与肖鸣宇教授分别为第二、第三作者。论文链接：https://www.sciencedirect.com/science/article/pii/S0890540126000416 该论文聚焦反应系统分析与综合中的关键问题，系统研究了彩色Muller博弈、Rabin博弈等多类重要正则博弈模型。作者综合运用递归、动态规划等方法，创新性地引入子博弈编码分析技术，构建了统一的判定算法框架，将多类正则博弈的求解复杂度由超指数时间成功降至指数时间，显著提升了相关问题的理论求解效率，为反应系统的自动化验证与综合提供了新的理论工具。本文首次将彩色Muller博弈问题的求解复杂度从超指数时间降低至指数时间。相关结果的对比在图1中给出。 第二篇论文题为“Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k”（突破3^k界限：Co-Path/Cycle Packing与Co-Path Packing问题的快速求解），第一作者为刘雨曦博士，指导老师肖鸣宇教授为第二作者。论文链接：https://www.sciencedirect.com/science/article/pii/S0890540126000040 该工作针对生物信息学中的重要图问题——Co-Path/Cycle Packing与Co-Path Packing，提出了突破性的参数化算法。研究结合路径分解、动态规划、Cut & Count技术及分支搜索方法，成功将Co-Path/Cycle Packing的确定性算法时间复杂度突破3^k的瓶颈，为相关图结构问题的算法设计与分析提供了重要技术参考。本文算法与已有结果的对比由图2给出。 第三篇论文题为“Improved Approximations for the Capacitated Vehicle Routing Problem with Fixed Capacity”（固定容量车辆路径问题的改进近似算法），第一作者为赵景阳博士，指导老师肖鸣宇教授为第二作者。论文链接：https://www.sciencedirect.com/science/article/abs/pii/S0890540126000039 该论文深入研究了组合优化领域的经典核心难题——容量限制车辆路径问题（CVRP）。针对单位需求、可分需求与不可分需求三种重要变体，作者提出了一系列新型近似算法，大幅改进了该问题原有的近似比理论界限。本文算法与已知最优算法的对比由图3给出。由图3可见，该工作在车辆容量固定且较小的情形下取得了显著突破。以单位需求和可分需求CVRP为例，相较于此前文献中的最佳结果，团队提出的新算法在各项容量参数下均实现了近似比的全面降低（图中加粗部分为本研究所取得的最优结果）。尤其在容量k=3,4,5等小容量场景下，近似比的优化尤为明显。在近似算法领域，近似比数值的降低意味着算法在“最坏情况”下给出的调度方案成本更加逼近理论上的绝对最优解。该研究不仅在理论计算机科学的经典路径分配问题上取得了实质性突破，也为现实世界中的物流配送调度、无人机载货路线规划以及具有严格载重限制的运输场景，提供了具有更优最坏情况保障的理论基础与算法支撑。

8月15至17日，第31届国际计算与组合学会议（The 31st International Computing and Combinatorics Conference，COCOON 2025）在成都举行，来自全球20多个国家和地区的百余位专家学者齐聚一堂，共襄盛举。会议由电子科技大学和中国计算机学会共同主办，计算机科学与工程学院（网络空间安全学院）算法与逻辑实验室承办，校长胡俊出席并致辞，实验室Bakh Khoussainov教授担任大会主席，学院副院长肖鸣宇教授和挪威卑尔根大学Fedor V. Fomin教授共同担任程序委员会主席。 胡俊代表学校向来自世界各地的专家学者表示热烈欢迎，并对COCOON 2025召开表示祝贺。他指出，会议所关注的基础性理论研究是人工智能、量子计算等颠覆性技术的基石。在当前全球科技竞争格局下，我们比任何时候都更需要重视基础理论研究，需要“从0到1”的原始创新。希望专家学者携手并进，共同推动理论计算机科学的发展，为人类科技进步贡献智慧力量。 Bakh Khoussainov教授介绍了算法与逻辑实验室团队的基本情况。他指出，该团队自成立以来，始终致力于算法理论与逻辑研究的前沿探索，汇聚了一批来自世界各地的顶尖学者和研究人员，并与多个国家和地区的科研机构建立了长期稳定的合作关系，在近几年取得一系列显著成果。 会议邀请了四位国际著名学者作主题报告。 来自清华大学的图灵奖获得者姚期智教授深入探讨了在人工智能、生物技术和量子计算时代，密码学面临的挑战与机遇，为与会者揭示了密码学在多学科交叉背景下的前沿发展方向。 印度数学科学研究所Saket Saurabh教授聚焦于覆盖和可满足性问题的固定参数近似算法，为解决复杂计算问题提供了新的思路和方法。 加拿大西门菲莎大学Andrei A. Bulatov教授从代数视角出发，为理解计算复杂性理论中的关键问题提供了新颖思路和深刻见解。 美国南加州大学Shang-hua Teng教授深入浅出地探讨了P+P与PSPACE之间的关系，为计算复杂性理论的研究注入了新的活力。 除邀请报告以外，会议还安排了54篇录用论文的分组报告。与会学者踊跃交流，就报告中的核心问题和未来研究方向展开深入讨论，现场学术氛围热烈。这些前沿成果的精彩呈现，不仅为与会者带来了一场学术盛宴，更推动了相关领域的创新与发展。

From February 28 to March 2, 2025, the 19th International Conference and Workshop on Algorithms and Computation (WALCOM 2025) was successfully convened in Chengdu, China, under the auspices of the Algorithms and Logic Lab. The conference was chaired by Bakh Khoussainov as the General Chair and Mingyu Xiao as the Program Committee (PC) Chair. The conference garnered 71 submissions from […]

We are pleased to announce the successful graduation of two exceptional Ph.D. candidates from the Algorithm and Logic Group at UESTC.Under the guidance of Prof. Mingyu Xiao, they have successfully completed their doctoral programs. Dr. Zimo ShengDissertation Title: Kernelization Algorigms for Graph Deleting and Packing ProblemZimo Sheng earned his bachelor’s degree in Computer Science and […]

2024年10月25日，第四届全国计算机科学技术名词审定委员会成立大会在浙江横店的圆明新园成功召开。肖鸣宇教授以其在计算机科学技术领域的卓越贡献和学术影响力，被选为第四届全国计算机科学技术名词审定委员会委员。 全国计算机科学技术名词审定委员会的职责包括制定计算机科学技术学科专业领域科技名词审定工作计划、审定原则和方法，以及审定科技名词等。名词审定工作对于科技领域的术语规范和传播至关重要，它不仅推动科技语言标准化，还促进科技成果共享及国际化传播。肖鸣宇教授的入选，不仅是对他个人学术成就的认可，也是对电子科技大学在计算机科学技术领域影响力的一种肯定。他将为我国计算机科学技术名词的规范化工作带来新的视角和动力，为科技创新和学术交流提供坚实的支撑。 附第四届全国计算机科学技术名词审定委员名单 顾 问： 林惠民 陆汝钤 郑纬民 主任委员： 梅宏 副主任委员：徐宗本 钱德沛 胡事民 陈熙霖 李国良 唐杰 文继荣 王昊奋 委 员（按姓名拼音排序）： 程学旗 高琳 郭兵 黄岚 黄庆明 黄萱菁 李克秋 梁吉业 林俊宇 栾家 马晓星 闵巍庆 宋志坚 孙晓明 唐志敏 田丰 王兴伟 王涌天 王忠杰 肖鸣宇 严明 于合龙 俞凯 於志文 詹乃军 张吉良 张莉 张文强 祝烈煌 委员兼秘书长：林俊宇 副秘书长： 彭鑫 张伟男 孔祥杰 李博涵 […]