-
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…
-
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…
-
Xiaoyang Gong: Word structures and their automatic presentations
Speaker: Xiaoyang Gong (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) September 12, 2025 (Friday) Venue: 518, Research Building 4 Abstract: We study automatic presentations of the structures $(\mathbb{N}; S)$, $(\mathbb{N}; E_S)$, $(\mathbb{N}; \leq)$, and their expansions by a unary predicate $U$. Here $S$ is the successor function, $E_S$ is…
-
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…
-
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…
-
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…