-
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最佳论文奖。
-
王艺源: 大规模离散优化问题求解算法
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比赛中获得两个赛道第一名，一个赛道第二名以及两个赛道第三名。
-
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. […]
-
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 […]
-
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
-
Weili (Lily) Wu: The Art of Big Data: Accomplishments and Research Needs
Speaker: () Time: 11:00-12:00 (Time in Beijing) June 11, 2024 (Tuesday) Venue: 518 Abstract: Speaker Bio: Dr. Weili (Lily) Wu received her MS and PhD degrees in computer science both from University of Minnesota, in 1998 and 2002 respectively. She is currently a full professor and a lab director of the Data Communication and Data […]
-
Boting Yang: On the One-Visibility Cops and Robber Game
Speaker: Boting Yang (The University of Regina) Time: 16:20-17:20 (Time in Beijing) May 30, 2024 (Thursday) Venue: 518, Research Building 4 Abstract: In this talk, we consider the one-visibility cops and robber game. The one-visibility cops and robber game is a variation of the classic cops and robber game, where one-visibility means that the information […]
-
Qingyun Chen: Survivable Network Design Revisited: Group-Connectivity
Speaker: Qingyun Chen (University of California, Merced) Time: 10:00-11:00 (Time in Beijing) May 14, 2024 (Tuesday) Venue: B1-104，Main building Abstract: In the classical survivable network design problem (SNDP), we are given an undirected graph with costs on edges and a connectivity requirement for each pair of vertices. The goal is to find a minimum-cost subgraph […]