-
Md. Saidur Rahman: Design of Enumeration Algorithms: A Tool to Assist 4IR
Speaker: () Time: 10:30-11:30 Beijing Time February 27, 2025 (Thursday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Dr. Md. Saidur Rahman, a professor (on deputation) of Bangladesh University of Engineering and Technology (BUET) and a fellow of Bangladesh Academy of Sciences, is currently serving as a member of University Grants Commission of Bangladesh. He […]
-
Venkatesan Guruswami: The Parameterized Inapproximability Hypothesis
Speaker: () Time: 9:00-10:00 Beijing Time February 26, 2025 (Wednesday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Venkatesan Guruswami is a Professor of Computer Science and Mathematics at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor’s degree from the Indian Institute of Technology, Madras, […]
-
Siyue Liu: Approximately Packing Dijoins via Nowhere-Zero Flows
Speaker: () Time: 16:20-17:20 Beijing Time Dec 13, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Siyue Liu is a Ph.D. student in the Algorithms, Combinatorics, and Optimization program at the Tepper School of Business, Carnegie Mellon University. Her research focuses on combinatorial optimization and integer programming. She has published in Mathematical Programming […]
-
Bingkai Lin: Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Speaker: () Time: 16:20-17:20 Beijing Time Dec 2, 2024 (Monday) Venue: 518, Research Building 4 Abstract: Speaker Bio: 林冰凯，南京大学计算机学院教授，博士生导师。博士毕业于日本东京大学，硕士及本科毕业于上海交通大学ACM试点班。研究领域是理论计算机科学，具体领域是参数复杂性(Parameterized Complexity) 及近似算法 (Approximation Algorithms)。主要成果包括独自解决了参数复杂性领域基础性难题——k-BICLIQUE问题的参数复杂性;在图嵌入问题参数复杂性的二分猜想这一长达十多年的公开问题上取得重要进展；对经典NP-难优化问题集合覆盖问题取得首个以及当前最好的参数算法不可近似比；证明了指数时间假设蕴含参数不可近似假设，推动了参数PCP理论的发展。成果获得理论计算机国际一流会议STOC 2024与计算机科学图论领域重要国际会议WG 2017最佳论文奖。两篇单独作者论文分别获国际算法会议SODA 2015最佳论文奖和最佳学生论文奖以及欧洲理论计算机重要会议ICALP 2019最佳论文奖。
-
Yike Chen: An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
Speaker: Yike Chen (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) November 15, 2024 (Friday) Venue: 518, Research Building 4 Abstract: The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem where a crane must traverse a graph with designated pairs of pickup and delivery points, moving […]
-
王艺源: 大规模离散优化问题求解算法
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 […]