Algorithms and Logic Group

Category: Seminars

  • 王艺源: 大规模离散优化问题求解算法

    Speaker: 王艺源 (Northeast Normal University) Time: 16:20-17:20 Beijing Time Nov 12, 2024 (Tuesday) Venue: 518, Research Building 4 Abstract: 大规模离散优化问题在许多实际应用中扮演着至关重要的角色，涉及物流、交通、资源分配、网络设计等多个领域。这类问题的复杂性源于其决策变量的离散性，通常需要在大量可能的解中寻找最优解。随着数据规模的不断增长和应用需求的日益复杂，传统的求解方法面临着效率和准确性的挑战。本次报告首先介绍求解算法效率的几种策略，包括克服循环搜索、基于变量依赖的预处理过程以及基于问题结构信息的启发式策略。之后，报告将重点围绕两个重要问题的求解：伪布尔优化问题和图同构问题。在伪布尔优化问题的研究中，提出了一种有效的局部搜索框架，显著提升了解的质量和求解的速度。针对图同构问题，提出了一种精确算法，提出了五个关键策略，包括更强的约束传播以简化顶点匹配域，引入结合点度数和解密度的匹配排序方法，以及自适应的约束传播机制。此外，为了更高效地求解大规模实例，提出了增强的边约束方法和域限制策略。实验结果表明，PathLAD+的性能显著优于当前多个最先进的精确算法。 Speaker Bio: 王艺源，男，东北师范大学信息科学与技术学院副教授，博士生导师，中国人工智能学会智能服务专委会委员，中国计算机学会理论计算机科学专委会委员，国际期刊IEEE-TLT专刊编委。2017年于吉林大学计算机科学与技术学院获得工学博士学位。2020年获得吉林省青年人才托举计划。主要从事人工智能、算法设计及其应用、逻辑推理、优化求解等方向研究，特别关注大规模组合优化问题求解等。主持并参与多项国家自然基金，在AIJ、JAIR、EJOR、AAAI、IJCAI、CP等上发表学术论文40余篇，其中以第一作者或通讯作者发表计算机学会推荐A类论文10余篇，并多次受邀担任IJCAI、AAAI等会议程序委员会委员。2022年国际MaxSAT比赛中包揽了完备组加权赛道和非加权赛道的冠军和亚军；2024年国际PBO比赛中获得两个赛道第一名，一个赛道第二名以及两个赛道第三名。

  • Bainian Hao: Inefficiency of the Pure Nash Equilibria in Structured Congestion Games

    Speaker: Bainian Hao (University of Wisconsin-Madison) Time: 16:20-17:20 Beijing Time Nov 8, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Congestion games are commonly used to model problems in large-scale networks and represent a simple, yet powerful paradigm for selfish resource sharing. These games belong to the larger class of potential games where the pure Nash equilibria is […]

  • Yiding Feng: Beyond Regularity: Simple versus Optimal Mechanisms, Revisited

    Speaker: () Time: 10:00-11:00 Beijing Time Nov 6, 2024 (Wednesday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Yiding Feng is an assistant professor at HKUST IEDA. Previously, he worked as a principal researcher at the University of Chicago Booth School of Business, and postdoctoral researcher at Microsoft Research New England. He received his Ph.D. […]

  • Chunyu Luo: A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem

    Speaker: Chunyu Luo (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) November 1, 2024 (Friday) Venue: 518, Research Building 4 Abstract: A $k$-defective clique of an undirected graph $G$ is a subset of its vertices that induces a nearly complete graph with a maximum of $k$ missing edges. The maximum […]

  • Lev D. Beklemishev: Provability and computability

    Speaker: Lev D. Beklemishev (Moskow State University) Time: 16:20-17:20 Beijing Time October 18, 2024 (Friday) Venue: 518, Research Building 4 Abstract: In this lecture we will give an introduction to the theory of computations and proofs. We will start with classical results such as decidable and undecidable problems and the Gödel incompleteness theorems. Then we […]

  • Chao Xu: An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

    Speaker: () Time: 10:30-12:00 Beijing Time Oct 17, 2024 (Thursday) Venue: 计算所环保园1号楼524会议室腾讯会议号：605 5793 9921，密码：图灵机被提出的年份（4位）B站直播网址：https://live.bilibili.com/22528138 Abstract: Speaker Bio: 许超，电子科技大学计算机科学与工程学院副教授，博士生导师，算法与逻辑团队成员。许超主要从事组合优化和算法的基础研究，在SODA、Mathematical Programming、SICOMP，等组合优化和算法的国际顶级期刊/会议上发表多篇学术论文。现主持国家自然科学基金优秀青年（海外）项目。

  • Markus Lohrey: Selected topics in streaming algorithms

    Speaker: () Time: 18:00-19:30 Beijing Time Sept 23, 2024 (Monday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Professor Markus Lohrey, Head of Theoretical Computer Science Group, The University of Siegen, Germany. His research interests are Decidability and complexity of problems in automata theory and algebra, Combinatorial Group theory, data compression, Logic in computer science […]

  • Qi Shi: Responsibility and Norms in Multiagent Systems

    Speaker: () Time: 16:20-17:20 (Time in Beijing) 11 September, 2024 (Tuesday) Venue: 518 Abstract: Paper Link: https://www.ijcai.org/proceedings/2024/394

  • Bakh Khoussainov: Deciding Regular Games: A Playground for Exponential Time Algorithms

    Speaker: () Time: 11:00-11:40 PT July 17, 2024 (Wednesday) Venue: Calvin Lab Auditorium @ University of California, Berkeley Online：Youtube Host： Simons Institute for the Theory of Computing Abstract: Speaker Bio: Bakh Khoussainov，教授，新西兰院士，电子科技大学计算机学院全职教授（我国西部地区引进的第一位发达国家的院士），目前担任电子科技大学算法与逻辑团队主任。他长期从事理论计算机科学中计算与逻辑领域的研究工作，2005年被新西兰最顶尖权威的学术组织——新西兰皇家学会评选为新西兰皇家学会院士，被评价为“在逻辑与理论计算机科学领域的领先专家，工作涉及对可计算性和复杂性理论的深入和非常广泛的研究”。2019年获得德国洪堡研究奖，该奖项旨在授予在基础研究、理论创新、学科引领等方面上取得了卓越成就的研究者。同年他还获得伦敦数学学会与新西兰数学学会联合授予的唯一Aitken Lecturer称号，该荣誉称号每两年仅授予一名最具杰出贡献的新西兰数学家（截至目前仅有包括美国工业与应用数学学会会士（SIAM Fellow）Hinke Osinga教授在内的5位研究者获此殊荣）。2017年他因其对于奇偶博弈问题的突出贡献荣获CCF A类会议ACM STOC 2017年最佳论文奖。他还曾获得新西兰数学学会研究奖，此奖项为新西兰数学领域最高奖，每年仅颁发给一名新西兰数学家，该奖项还曾颁发给包括美国数学学会会士G. Martin, R. Downey教授（AMS Fellow）, M. Conder教授（AMS Fellow）等优秀数学家。

  • 肖鸣宇: 智能决策中的打分融合问题/ Score Aggregation in Intelligent Decision-Making

    Speaker: () Time: 10:40-11:20 (Time in Beijing) August 10, 2024 (Saturday) Venue: 北京友谊宾馆友谊宫第 8 号会议室 腾讯会议/ VooV Meeting： 409-540-830 Host： Beijing Institute of Technology (BIT) Abstract: Speaker Bio: 肖鸣宇，中国计算机学会理事、理论计算机科学专委员会主任；电子科技大学计算机科学与工程学院教授，副院长，算法与逻辑实验室执行主任，国家级信息与网络安全虚拟仿真实验教学中心主任，国家级计算机实验教学示范中心主任。致力于算法、组合优化、机制设计、算法博弈论等方面的基础理论研究，在精确算法、参数算法、核心化算法等领域是国内外著名的专家，为电路满足问题（SAT）、最大独立集等多个基本NP难问题设计了当前最佳的精确算法和参数算法；并将算法理论应用于人工智能、工业优化、计算经济、运筹学等领域中取得了显著成效。近年来在算法理论、人工智能基础算法领域顶级期刊和会议上以单独作者和主要作者发表论文超过150篇，撰写英文专著1部，主持国家级项目10余项。