-
Saket Saurabh: Picking Random At Vertices
Abstract: We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set.…
-
Jie Xue: Fine-Grained Bounds for Courcelle’s Theorem
Speaker: Jie Xue(New York University Shanghai) Time: 16:20-17:20 Beijing Time June 4, 2026 (Thursday) Venue: 四号科研楼A区 518 Abstract: Courcelle’s theorem is one of the most celebrated algorithmic meta-theorems and has brought a profound impact on the theory of parameterized complexity. The theorem states that every graph property expressible by a monadic second-order (MSO) formula ϕ…
-
Yike Chen: Discrete Unimodal-Cost p-Median on a Line.
Speaker: Yike Chen (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) May 22, 2026 (Friday) Venue: 518, Research Building 4 Abstract: This talk studies the Unimodal-Cost k-Median problem: given n piecewise-linearunimodal functions f_1,…,f_n: R -> R, choose k facilities y_1,…,y_k in R to minimize \sum_i \min_r f_i(y_r). The classical special…
-
Kangyi Tian: Representative Family and Its Applications
Speaker: Kangyi Tian (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) May 15, 2026 (Friday) Venue: 518, Research Building 4 Abstract: Since it was systematically developed for parameterized algorithms in [Fomin et al., JACM 2016], the Representative Family technique has become a powerful tool in parameterized algorithm design. In this…
-
Wenfei Fan: Beyond LLMs: A Multi-Paradigm AI Approach
Speaker: 樊文飞 (Shenzhen Institute of Computing Sciences) Time: 10:00-11:30 Beijing Time May 14, 2026 (Thursday) Venue: 四号科研楼A区 518 Abstract: Large Language Models (LLMs) are transforming many applications, yet their use in industrial and high-stakes settings remains limited. LLMs often suffer from hallucinations, limited interpretability, weak explicit reasoning, and heavy data dependence, making it difficult to…
-
Yiping Liu: A Reduction-Driven Local Search for the Generalized Independent Set Problem
Speaker: Yiping Liu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 17, 2026 (Friday) Venue: 518, Research Building 4 Abstract: The Generalized Independent Set (GIS) problem extends the classical maximum independent set problem by incorporating profits for vertices and penalties for edges. This generalized problem has been identified in…
-
Chao Xu: AI-Assisted Mathematics in Practice: Tools, Workflows, and a Case Study
Speaker: Chao Xu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) April 3, 2026 (Friday) Venue: 518, Research Building 4 Abstract: Large language models are useful research assistants in theoretical computer science — generating examples, writing scripts, triaging literature, stress-testing conjectures, and contributing to proofs. This talk gives a brief…
-
Xiaoyang Gong: Maltsev Constraints are tractable
Speaker: Xiaoyang Gong (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 20, 2026 (Friday) Venue: 518, Research Building 4 Abstract: One of the most sighificant achievements in the study of Constraint Satisfaction Problems (CSPs) is a result due to Bulatov [ECCC 2002], which establishes that every constraint language $\Gamma$…
-
Xinyao Wang: A journey through constraint satisfication problem.
Speaker: Xinyao Wang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 13, 2026 (Friday) Venue: 518, Research Building 4 Abstract: Computational problems exhibit a wide range of behaviors in terms of how efficiently they can be solved. What underlying mathematical structure in a problem enables an efficient algorithm, and…
-
Ce Jin: New Algorithms for Pigeonhole Equal Subset Sum
Speaker: () Time: 11:00-12:00 Beijing Time January 5, 2026 (Monday) Venue: 四号科研楼A区 518 Abstract: Speaker Bio: Ce Jin is a Miller Postdoctoral Fellow at UC Berkeley. He completed his PhD at MIT in 2025. Before that, he was an undergraduate student in Yao Class, Tsinghua University. He has a broad interest in theoretical computer science.