-
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 […]
-
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 […]
-
Guanghao Ye: Nested Dissection Meets IPMs: Fast Algorithms for Flows and LPs in Separable Graphs
() Time: 10:00-11:00 (Time in Beijing) January 19, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Guanghao Ye is a PhD student at MIT EECS, advised by Jon Kelner. He previously earned his Bachelor’s and Master’s degrees at the University of Washington, under the supervision of Yin Tat Lee. His research broadly focuses […]