Algorithms and Logic Group

Category: News and Announcements

  • 算法与逻辑团队本科生在理论计算机科学领域重要会议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

  • Professor Yuxi Fu will offer a short course on Advanced Computational Complexity

    博士前沿课程-计算复杂性理论 主讲人： 傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起在上海交通大学任职，历任计算机系主任，软件学院院长。是国家杰出青年基金获得者、上海市优秀学科带头人。研究领域为理论计算机科学，内容涉及程序理论、并发理论、等价性验证、可达性理论、交互理论等。学术兼职有：上海高校软件理论研究中心主任、国务院学位委员会第六届学科评议组成员 (2010-2014)、上海市计算机学会理事长 (2015-2018）、教育部计算机类专业教学指导委员会副主任 （2013-2017，2018-2022）。是Mathematical Structuresin Computer Science期刊的编委。傅育熙讲授的 《计算复杂性理论》课程获得“2019年度高校计算机专业优秀教师奖励计划”。 课程包含两部分：一、随机计算与去随机，主要内容包括：随机算法、概率图灵机与BPP、通用哈希函数族、随机游走、扩张图及其显式构造、Reigold定理。二、交互证明系统，主要内容包括：私币交互证明系统、公币交互证明系统、两类交互证明系统的等价性、IP=PSPACE、多证明者交互证明系统。参考教材：《计算复杂性理论》（傅育熙著、清华大学出版社，2023年）。 上课时间： 17-17周，星期一第3-4节 第5-6节 星期二第3-4节第5-6节 星期三第3-4节 第5-6节 星期四第3-4节 第5-6节 星期五第1-4节 上课地点：立人楼A108

  • 算法与逻辑团队学子获2023华为嵌入式软件大赛全国总决赛算法组季军

    6月3日，2023年华为“追光者”嵌入式软件大赛总决赛在华为松山湖欧洲小镇落下帷幕，由算法与逻辑团队研一学生罗春雨、研一学生解智超和本科生王正仁组成的“icecreamx3”队荣膺大赛算法组全国季军。  大赛决赛参赛同学合影 大赛获奖证书 左五起：解智超、王正仁、罗春雨 华为嵌入式软件大赛是面向在校大学生的软硬件作品比赛，分为算法组和实物组两个赛道，由算法与逻辑团队派出的”icecreamx3”队参加了算法组的比赛。算法组的赛题通常源自ICT领域的实际问题，本届赛题抽象为光网络的加纤扩容难题，参赛者需要提出并实现最优化算法使其能够在2min之内安排完所有光业务并使光网络的加纤总成本最小。 经过五大赛区区域初赛、复赛层层选拔，算法组&实物组共36支队伍晋级总决赛，共聚松山湖总部进行现场对决。最终，经过现场四个小时的激烈角逐，团队成员沉着冷静、有条不紊，在时间十分紧迫的情况下出色地完成了比赛，在18支算法组的队伍中脱颖而出，获得了全国季军的优异成绩。  

  • Prof. Bakh Khoussainov’s talk at Beijing Logic Meeting

    Prof. Bakh Khoussainov is an invited speaker at Beijing Logic Meeting. See http://www.amss.cas.cn/xshy/202304/t20230417_6739972.html for details.

  • 实验室学生勇夺大学生数学竞赛全国第一名

    最近，从中国数学会传来好消息，算法与逻辑团队2019级本科生史可同学在第14届全国大学生数学竞赛决赛中以总分97.5分勇夺全国非数学专业第一名。据悉本次竞赛有来自全国1024所高校的23万多学生参加。在众多优秀选手中获得全国第一名实属不易。 史可同学在算法与逻辑团队学习的一年多时间里，科研方面也取得了突出的成绩，完成了两篇论文，其中一篇被算法领域顶级会议SODA 2023接收。

  • Binglin Tao will defend her Ph.D. thesis on May 31, 2023

  • 祝贺！算法与逻辑实验室教授当选欧洲科学院院士！

    近日，欧洲人文和自然科学院（Academia Europaea，简称“欧洲科学院”）发布2023年新增院士名单，电子科技大学计算机科学与工程学院（网络空间安全学院）Khoussainov Bakhadyr教授当选。 Khoussainov Bakhadyr教授，新西兰皇家学会院士，国家人才计划入选者。现任电子科技大学计算机科学与工程学院（网络空间安全学院）算法与逻辑实验室负责人。 算法与逻辑团队成员Khoussainov Bakhadyr教授长期从事理论计算机科学中计算与逻辑领域的研究工作，研究方向包括逻辑与计算，已在理论计算机科学领域发表了160余篇具有国际影响力的高水平国际期刊/会议论文，其卓越的学术成就得到国际学术界的广泛认可，于2021年获得Nerode Prize，2019年获得德国洪堡研究奖，2017年荣获STOC会议最佳论文奖（STOC在整个计算机科学领域享有崇高声望）。2002年获得新西兰数学学会研究奖，2019年获得伦敦数学学会与新西兰数学学会联合授予的唯一Aitken Lecturer称号。 Bakh教授给博士生上“计算机科学中的数学基础”课程 Khoussainov Bakhadyr教授于2021年全时全职加入电子科技大学计算机科学与工程学院（网络空间安全学院），是学院首位全时全职引进的海外院士。现已组建了一支6人规模“小而精”的研究团队，其中团队成员50%为外籍学者。主持了包括国家自然科学基金、德国洪堡研究基金、新西兰皇家学会Marsden基金等在内的多个国内外项目。 欧洲人文和自然科学院（简称“欧洲科学院”）是欧盟的“国家科学院”和法定科学顾问，由英国皇家学会与欧洲各国的国家科学院共同发起并于1988年成立，总部位于英国伦敦。作为国际上跨地域和学术领域最广泛、学术地位最高、影响最大的科学组织之一，欧洲科学院的院士包括自然科学、生命科学、社会科学、人文科学等领域的顶级学者，主要在欧洲各国的院士中遴选，代表着欧洲人文和自然科学界最高的科学水平和学术地位。

  • 算法与逻辑团队本科生一作论文被计算机领域顶级会议IJCAI接收

    近日，第32届国际人工智能联合会议IJCAI（International Joint Conference on Artificial Intelligence）放榜，我校计算机科学与工程学院（网络空间安全学院） 2019级本科生王正仁以第一作者身份撰写的关于松弛团搜索问题的论文《A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap》被接收，届时该学生将在会议上展示成果并进行学术报告。该论文是在电子科技大学算法与逻辑团队周毅副教授（通讯作者）和肖鸣宇教授指导下完成，参与作者还有硕士生罗春雨同学。这也是王正仁同学继WWW 2022之后，本科阶段以第一作者发表的第二篇CCF-A类会议论文。

  • 冠军+季军！算法与逻辑团队学子在2023华为软件精英挑战赛全球总决赛中再创佳绩

    4月23日，2023华为软件精英挑战赛全球总决赛在深圳华为总部举行，肖鸣宇教授指导的“_______（下划线）队”夺得了全球总决赛冠军，CHAO XU教授指导的“划水小队不划水队”夺得了全球总决赛季军，创造学校参赛以来历史最好成绩。