Algorithms and Logic Group

Category: Paper

  • 电子科技大学算法与逻辑团队在EC 2026上发表重要理论成果

    近日，我校计算机科学与工程学院（网络空间安全学院）算法与逻辑团队在经济与计算交叉研究领域取得重要突破，论文《Contracting with a Mechanism Designer》被经济与计算领域顶级国际会议2026 ACM Conference on Economics and Computation（简称EC 2026）正式录用。这是团队在计算经济学方向上的标志性成果，彰显了学校在国际前沿交叉学科中的研究实力。EC会议专注于经济学与计算机科学的交叉研究，是该领域的顶级国际会议之一。本届会议共收到1115篇全文投稿，最终仅录用290篇，录用率约为26.0%。该论文由电子科技大学计算机科学与工程学院（网络空间安全学院）算法与逻辑团队肖鸣宇教授及其博士生刘耀壕与香港科技大学冯逸丁教授等国内外合作者共同完成。该论文聚焦现代众包市场中的三方经济交互，提出了一种全新的“委托人-中介-代理人”博弈模型（如图1所示），系统刻画了雇主（委托人）、平台（中介）与工人（代理人）之间的合约与机制设计问题，为理解众包平台中的合约设计与中介定价策略提供了系统的理论框架。 作者完整求解了该模型的子博弈完美均衡，发现委托人的最优合约可等价转化为虚拟价值定价问题，并证明了线性合约的最优性。图2展示了已知与未知市场大小两种情形下，中介参与带来的效用损失上界：当市场大小已知时，损失仅取决于工人成本的分布特征，在理想情况下可被控制在常数倍以内；当委托人只知道市场大小的范围时，损失还会额外受到该范围宽度的放大影响，不确定性越大，效率损失越严重。 电子科技大学算法与逻辑团队由欧洲科学院院士、新西兰院士Bakh Khoussainov教授和算法专家肖鸣宇教授共同组建，现有许超教授、Toru Takisaka教授、周毅副教授、郝东副教授等多位骨干成员。团队长期深耕算法设计与分析（包括近似算法、参数算法、精确算法、在线算法等），逻辑、图论与图算法，组合优化，算法工程，机制设计与算法博弈论，形式化方法与认证等理论方向，近年来在LICS、CAV、WINE、SODA等理论计算机科学领域顶级会议上连续发表高水平成果，研究实力和学术影响力稳步提升。此次EC 2026论文的录用，进一步彰显了团队在计算经济学前沿领域的国际竞争力。算法与逻辑团队将以此次突破为契机，继续聚焦算法博弈论与机制设计的基础理论问题，深化国际合作，产出更多原创性成果，为推动我国在计算经济学领域的发展贡献成电智慧。 论文信息如下 (按照理论计算机科学/计算经济学国际学术惯例，论文作者按照姓氏首字母排序)： Contracting with a Mechanism Designer Authors: Tian Bai, Yiding Feng, Yaohao Liu*, Mengfan Ma, Mingyu Xiao 论文链接：https://arxiv.org/pdf/2507.12054

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