Algorithms and Logic Group

Category: Seminars

  • 肖鸣宇: 智能决策中的打分融合问题/ 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余项。

  • 肖鸣宇: 图多路分割问题的快速精确算法

    肖鸣宇 (University of Electronic Science and Technology of China) Time: 09:30-10:30 (Time in Beijing) July 4, 2024 (Thursday) Venue: Online, Tencent Meeting: 547-454-448 Host: Nankai University （南开大学） Abstract: 经典的最小割问题是通过删除图中最少的顶点将图中两个终端顶点分割开来，这个问题的一个自然推广就是将图中多个终端顶点相互分割开来，这就是图多路分割问题(The MultiwayCut Problem)。尽管最小割问题存在快速的多项式算法，但是当需要分割3个或者更多终端顶点的时候，这个问题就变成了NP难的。对图多路分割问题来说，经典的最大流最小割这一对偶性质不存在了，找到一个比简单穷举搜素算法更快的算法也不容易。在无向图上，图多路分割问题目前最好的精确算法可以做到 时间，其中n是图中顶点的个数。在有向图上是否存在比简单穷举算法 时间更快的算法却一直是一个未解决的公开难题。本文将介绍在有向图上如何在时间内解决图多路分割问题。 Speaker Bio: 肖鸣宇，现为电子科技大学计算机科学与工程学院教授，副院长算法与逻辑实验室执行主任;中国计算机学会理事、理论计算机科学专业委员会主任;国家级信息与网络安全虚拟仿真实验教学中心主任国家级计算机实验教学示范中心主任。致力于算法、计算理论、图论与图算法、机制设计与算法博弈论等方面的基础理论研究，为SAT、最大独立集等多个基本NP难问题设计了当前最佳的精确算法和参数算法;并将算法理论应用于人工智能、工业优化、计算经济、运筹学等领域中取得了显著成效。近年来在算法理论、人工智能基础算法领域顶级期刊和会议上以单独作者和主要作者发表论文超过150篇，撰写英文专著1部。主持国家级科研项目10余项。

  • 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 […]

  • Toru Takisaka: Lexicographic Ranking Supermartingales with Lazy Lower Bounds

    Speaker: Toru Takisaka (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) May 10, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Lexicographic Ranking SuperMartingale (LexRSM) is a probabilistic extension of Lexicographic Ranking Function (LexRF), which is a widely accepted technique for verifying program termination. In this paper, we are the […]

  • Andre Nies: Prime numbers, factorisation, and algorithms

    Speaker: Andre Nies (The University of Auckland) Time: 16:20-17:20 (Time in Beijing) April 19, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Euclid in around  300 BC proved that the sequence of prime numbers is infinite. This sequence starts 2,3,5,7,11, 13, …; the largest currently known prime number  is  obtained by raising 2 to the […]

  • Alexander Zapryagaev: Presburger arithmetic and related theories

    Speaker: Alexander Zapryagaev (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 12, 2024 (Friday) Venue: 518, Research Building 4 Abstract: The talk introduces Presburger arithmetic PrA, the theory of natural numbers with addition, and Büchi arithmetics BA_n, a series of algorithmically decidable extensions of PrA. The main logical and […]

  • Junqiang Peng: A Fast Algorithm for MaxSAT Above Half Number of Clauses

    Speaker: Junqiang Peng (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 29, 2024 (Friday) Venue: 518, Research Building 4 Abstract: In the MaxSAT problem, given a CNF formula with clauses and an integer , we are asked whether there is a truth assignment that satisfies at least clauses of […]

  • Yinyu Ye: Online Market Design: Dynamic Equilibrium Pricing

    () Time: 11:00-12:00 (Time in Beijing) March 25, 2023 (Monday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Yinyu Ye is currently the K.T. Li Professor of Engineering at Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering, Stanford University. His current research topics include Continuous and Discrete Optimization, Data Science […]