-
Celebrating the Graduation of Two Outstanding Ph.D. Students
We are delighted to announce the graduation of two remarkable Ph.D. students from the Algorithm and Logic Lab at UESTC.Under the guidance of Prof. Mingyu Xiao, they have successfully completed their doctoral programs. Dr. Tian BaiDissertation Title: Investigations Concerning Parameterized and Exact Algorithms for the Feedback Set and Related Problems. Tian Bai earned his bachelor’s […]
-
Ton Kloks offers a short course on Graph Algorithms
逻辑与算法团队协议研究员Ton Kloks从2024年6月17日起为我校师生开设为期8天的《图算法导论》短期课程。 在《图算法导论》这门课程中，Ton Kloks从图论概念、算法、问题模型、前沿趋势四个部分带大家进入图算法的世界。由一些图论概念展开，介绍了早期图算法中的一些经典结果，之后对图代数和一元二阶逻辑进行了简要介绍，最后以“树宽”概念为跳板，阐述了相关方向的研究趋势。Ton Kloks教授善于深入浅出，让本科生也有机会了解当前图论和图算法中最重要和最前沿的理论。 本次课程使用的教材是Ton Kloks教授和肖鸣宇教授合著的《A guide to graph Algorithms》（中文：《图算法导论》），该教材在两位作者持续多年的交流和实践中不断地丰富和完善之后，经由国际著名出版社Springer于2022年出版。 Ton Kloks教授曾先后在埃因霍温科技大学、利兹大学、香港中文大学等十余所高校和研究机构担任教师和研究员，具有丰富的研究和教学经验。近年来，应电子科技大学计算机科学与工程学院副院长肖鸣宇教授的邀请，Ton Kloks教授多次前来共同讲授图算法方面的短期课程，曾连续开设了4年，都取得较好的教学效果。 上课时间：2024年6月17日-6月26日 10：20-12：00 上课地点：品学楼B213
-
算法与逻辑团队在计算机理论方向多个顶级国际会议上实现突破
近日，电子科技大学计算机科学与工程学院（网络空间安全学院）算法与逻辑团队先后在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 […]
-
Our Team Will Hold ALC 2027
The 19th Asian Logic Conference will be held in autumn, 2027, in Chengdu, China. Organized by the Algorithms and Logic Lab of University of Electronic Science and Technology of China (UESTC). Professor Bakh Khoussainov will serve as the Chair of the conference. The Asian Logic Conference (ALC) is a major international event in mathematical logic and its applications. It features […]
-
Alexander Zapryagaev joined the group as postdoc
Alexander Zapryagaev has finally joined the group as postdocs. He works on Formal arithmetics, interpretations and automatic structures.
-
我校肖鸣宇教授当选中国计算机学会理论计算机科学专委主任
近日，中国计算机学会（CCF）理论计算机科学专业委员会召开全体会议，选举产生了新一届专委会领导机构，并在北京完成了新老主任交接工作。我校计算机科学与工程学院（网络空间安全学院）肖鸣宇教授当选新一届CCF理论计算机科学专业委员会主任。这是我校老师首次担任中国计算机学会专委会主任一职，将对提升我校在计算机学科的影响力、推动相关学科建设与发展起到积极作用。 中国计算机学会（CCF）是全国一级学会。CCF理论计算机科学专委会成立于1983年，是理论计算机科学方向全国成立最早且规模最大的学术组织，该组织旨在促进国内计算机科学理论的学术研究和交流，推动算法等传统理论方向的发展，开拓新兴的理论方向，促进“理论联系实际”的前沿和交叉研究等。经过多年的建设与发展，目前专委会已成为拥有8个专业学组和3个工作组织的学术性团体。 肖鸣宇目前是计算机科学与工程学院（网络空间安全学院）教授，副院长，算法与逻辑实验室执行主任，国家级实验教学示范中心主任，国家级虚仿实验教学中心主任，中国计算机学会理事和杰出会员。 肖鸣宇教授长期致力于算法、计算理论、图论与图算法、机制设计与算法博弈论等方面的基础理论研究；在国内外是精确算法、参数算法、核心化算法等领域的著名专家，为SAT、最大独立集等多个基本NP难问题设计了当前最佳的精确算法和参数算法；并将算法理论应用于人工智能、工业优化、计算经济、运筹学等领域，且取得了显著成效。近年来在Information and Computation、JCSS、Algorithmica、ACM\IEEE Trans.、AAAI、IJCAI、ICALP、INFOCOM、WWW等算法理论、人工智能基础算法领域顶级期刊和会议上发表论文超过130篇，撰写英文专著1部。
-
We won COCOON 2023 best paper award
In recent days, there has been good news from the 29th International Computing and Combinatorics Conference (COCOON 2023), where a paper titled “Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing” co-authored by Dr. Zhao Jingyang and Professor Xiao Mingyu from our Algorithms and Logic group has won the “Best Paper Award”. COCOON is an important […]
-
Our Team Will Hold COCOON 2025 and WALCOM 2025
We recently received news that our Algorithm and Logic group has been granted the hosting rights for two important theoretical computer science conferences: COCOON 2025 and WALCOM 2025. Professor Bakh Khoussainov will serve as the General Chair for both conferences, while Professor Mingyu Xiao will be the PC Co-Chair for both conferences. COCOON (Conference on […]
-
算法与逻辑团队本科生在理论计算机科学领域重要会议COCOON上发表研究成果
近日，我校计算机科学与工程学院（网络空间安全学院）计算机科学与技术专业2020级本科生田康毅以第一作者身份在CCF理论计算机科学领域B类会议COCOON上发表题为《Parameterized Algorithms for Cluster Vertex Deletion on Degree-4 Graphs and General Graphs》的论文。计算机（网安）学院算法与逻辑团队的肖鸣宇教授为第二作者和通讯作者，加拿大里贾纳大学的Boting Yang教授为第三作者。 该论文研究了著名的聚类点删除问题（CVD问题）的算法与计算复杂性，得到该问题精确求解中，以点删除集大小k为参数的最佳运行时间上界，改进了Tsur于2021年给出的结果。本文给出的时间运行界和历史上该问题的运行时间如表1中所示。 CVD问题是图算法中一个著名的NP难问题，该问题问是否能通过删除图中不超过k个顶点使得剩下图中每一个连通块都是一个完全图。由于CVD问题良好地刻画了聚类的性质，该问题在机器学习和计算生物学中有着广泛的应用。本论文首先针对低度图上的CVD问题进行了分析，在度数不超过4的图上先设计了一个快速的算法；然后在4度图的结果基础上，使用自动生成搜索树（Automated Generation of Searching Trees）的技术对一般图进行了深入分析，最终改进该问题当前最好的算法。 田康毅同学从大一开始进入算法与逻辑团队学习，在肖鸣宇教授的指导下从事参数算法与核心化算法相关方向的研究工作，已经研究获得多项科研成果，形成学术论文两篇。
-
算法与逻辑团队在理论计算机科学领域顶级期刊Information and Computation上发表研究成果
近日，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队2021级博士生彭俊强以第一作者身份在CCF理论计算机科学领域A类期刊Information and Computation (I&C)上发表题为《Further improvements for SAT in terms of formula length》的论文。论文第二作者和通讯作者为肖鸣宇教授。 该论文研究了著名的布尔可满足性问题（SAT问题）的算法与计算复杂性，得到该问题精确求解中，以问题输入CNF公式的总长度L为度量的当前最佳运行时间上界，改进了十余年前Chen和Liu于2009年给出的结果。本文给出的时间运行界和历史上该问题的运行时间界如表1中所示。 SAT问题是第一个被证明的NP完全问题，在计算复杂性理论里扮演着重要角色，也在人工智能、运筹学和电子设计工程等众多领域中有着重要且基础的应用。该经典问题的运行时间上界在过去几十年里一直被深入研究。作者们通过设计新的分支算法，并运用测量治之（Measure-and-Conquer）的分析技术深入分析，最终取得了这项突破。 彭俊强同学为计算机（网安）学院2021级直博研究生。他从本科阶段开始进入算法与逻辑团队学习，在肖鸣宇教授的指导下从事SAT及其相关问题的研究工作。在博士学习的前两年已经发表两篇CCF A类和一篇CCF B类论文。 算法与逻辑团队由欧洲科学院院士、新西兰院士Bakh Khoussainov教授和肖鸣宇教授共同组建，周毅副教授、郝东副教授和许超助理教授、日籍Toru Takisaka副研究员等多位老师参与。该团队致力于基础理论研究，以探索算法难题和解决重要的科学问题为宗旨，激发和培养学生及青年老师对算法和基础理论的兴趣，为算法及相关研究方向感兴趣的师生提供一个交流平台。团队目前重点关注的研究方向包括：算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等）、逻辑、图论与图算法、组合优化、算法工程、机制设计与算法博弈论、形式化方法与认证等。 团队以科研育人为首要任务，培养出了众多优秀的学生。近两年本科生第一作者在WWW、IJCAI、SODA、COCOON、Discrete Mathematics等CCF A类会议和重要刊物上发表5篇论文。除论文外，团队学生还在多项科技竞赛中斩获重要奖项，仅2023年上半年就获得2023年华为软件精英挑战赛全球总决赛冠军，2023年全国大学生数学竞赛（非数学类）全国第一名，IEEE极限编程竞赛世界第四名（第五次进入世界前十名）等。 论文链接：https://www.sciencedirect.com/science/article/pii/S0890540123000883