Category: Weekly Seminars

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

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

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

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

  • Zihui Liang: Two new algorithms for solving Muller games and their applications

    Speaker: Zihui Liang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 22, 2024 (Friday) Venue: 518, Research Building 4 Abstract: Muller games form a well-established class of games for model checking and verification. These games are played on directed graphs $\mathcal G$ where Player 0 and Player 1 play […]

  • Lu Liu: A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem

    Speaker: Lu Liu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 15, 2024 (Friday) Venue: 518, Research Building 4 Abstract: The maximum vertex-weighted clique problem (MVWCP) and the maximum edge-weighted clique problem (MEWCP) are two natural extensions of the fundamental maximum clique problem. In this paper, we systematically study […]

  • Yi Zhou: Recent advances in algorithms for k-plex problems

    Speaker: Yi Zhou (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) March 8, 2024 (Friday) Venue: 518, Research Building 4 Abstract: In the field of graph mining, the k-plex is a well-known extension of the clique model. A k-plex is nearly a clique except that each vertex is allowed to […]