Algorithms and Logic Group

Category: Paper

  • 算法与逻辑团队在理论计算机科学领域顶级期刊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

  • 算法与逻辑团队本科生一作论文被计算机领域顶级会议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类会议论文。

  • Our LAB has one SIGIR paper accepted

    Our LAB has one SIGIR paper accepted.The title is “Contrastive Learning for Signed Bipartite Graphs”.The authors are Zeyu Zhang, Jiamou Liu, Kaiqi Zhao, Song Yang, Xianda Zheng, and Yifei Wang.

  • An undergraduate in our lab published research results in the prestigious journal Discrete Mathematics

    Discrete Mathematics is one of the famous journals in discrete mathematics and combinatorics. The research areas covered by Discrete Mathematics include graph and hypergraph theory, enumeration, coding theory, block designs, the combinatorics of partially ordered sets, extremal set theory, matroid theory, algebraic combinatorics, discrete geometry, matrices, discrete probability, and parts of cryptography. Our paper has been […]

  • We got three papers accepted by AAAI 2023

    Our lab has three papers accepted by AAAI 2023. The information about the papers is below: Facility Location Games with Entrance Fees, by Mengfan Ma (Ph.D. Student), Mingyu Xiao, Tian Bai (Ph.D. Student), Bakh Khoussainov. The Linear Distance Traveling Tournament Problem Allows an EPTAS, by Jingyang Zhao (Ph.D. Student), Mingyu Xiao. MSDC: Exploiting Multi-State Power […]

  • One paper accepted by WWW 2022

    The Web Conference (WWW) is the premier international venue focused on understanding the current state and the evolution of the Web through the lens of computer science, computational social science, economics, policy, and many other disciplines. The 31th Web Conference (WWW 2022) will be hosted by Lyon, France from April 25th to 29th. This year, […]

  • We got one paper accepted by AAAI 2022 in the full paper

    AAAI Conference on Artificial Intelligence (AAAI) is a top conference in AI. The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) will take place in Vancouver. This year, the conference received a record 9,251 submissions, of which 9,020 were reviewed. Based on a thorough and rigorous review process, 1,349 papers have been accepted. This yields an […]

  • We got one paper accepted by INFOCOM 2022 in the full paper

    IEEE INFOCOM is a top-ranked conference on networking in the research community. It is a major conference venue for researchers to present and exchange significant and innovative contributions and ideas in the field of networking and closely related areas. IEEE INFOCOM covers both theoretical and systems research. For INFOCOM 2022, the acceptance ratio is 19.9%. […]

  • Three papers accepted by IJCAI, SAT and ICML

    Recently, we have three papers accepted by IJCAI, SAT and ICML. International Joint Conferences on Artificial Intelligence (IJCAI) is a top conference in AI. Our group got one paper accepted by IJCAI 2021. The International Conferences on Theory and Applications of Satisfiability Testing (SAT) is the premier annual meeting for researchers focusing on the theory […]

  • We got one paper accepted by WWW 2021 in the full paper track

    The Web Conference (WWW) is the premier international venue focused on understanding the current state and the evolution of the Web through the lens of computer science, computational social science, economics, policy, and many other disciplines. The 30th Web Conference (WWW 2021) will take place in Ljubljana, the capital of Slovenia. This year, the conference […]