滕尚华Shang-Hua Teng
南加州大学University of Southern California
演讲时间：6 月 19 日 09:10-10:10Talk time: June 19, 09:10-10:10
报告题目: P+P ≧ PSPACE: Deep Logic, Strategic Losing, and Game Secrets
摘要
A combinatorial game is defined by a succinct ruleset specifying game positions and the set of feasible options each player can move to from every position. In the normal-play setting, two players take turns advancing the game, and the player who is forced to play at a terminal position, a position with no feasible options, loses the game. Playing combinatorial games optimally usually requires deep strategic reasoning about long alternation down to the last level of their game trees and is typically PSPACE-hard. In Combinatorial Game Theory (CGT), the disjunctive sum (or sum for short) of any two games G and H, denoted by G + H, is a game in which the next player chooses to make a move in exactly one of G and H, leaving the other alone.
In this talk, we show that the sum of two polynomial-time solvable games can be PSPACE-hard. In other words, we prove P+P ≧ PSPACE when P and PSPACE, respectively, represent the families of polynomial-time and polynomial-space solvable games, and + denotes the disjunctive sum. Our result has computational implications for classical Sprague-Grundy Theory (1930s), which shows that the Grundy value, a concept generalizing winnability, of the disjunctive sum of any two impartial games can be computed in polynomial time from their Grundy values. In contrast, we prove that, assuming PSPACE ≠ P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum. Our results settle two long-standing complexity-theoretical questions, open since 1981 and 1993 in CGT, concerning the computational complexity of strategic losing for the goal of winning the overall sum game. I will also draw a connection between our main theorem and a famous Chinese idiom, in honor of the legendary strategist in Chinese history, 諸葛亮 (Zhuge Liang), who is beautifully depicted in the classic novel 三國演義 (The Romance of the Three Kingdoms).
Joint work with Kyle Burke (Florida Southern College) and Matt Ferland (Dickinson College).
Shang-Hua Teng is a USC University Professor of Computer Science and Mathematics. He is a fellow of SIAM, ACM, and the Alfred P. Sloan Foundation, and has twice won the Gödel Prize: first in 2008 for developing smoothed analysis, and then in 2015 for designing the breakthrough scalable Laplacian solver. Citing him as “one of the most original theoretical computer scientists in the world,” the Simons Foundation named him a 2014 Investigator to pursue long-term curiosity-driven fundamental research. He also received the 2009 Fulkerson Prize, the 2023 Science & Technology Award for Overseas Chinese from the China Computer Federation, the 2021 and 2025 ACM STOC Test of Time Awards (for smoothed analysis and max-flow computation), and the 2022 ACM SIGecom Test of Time Award (for settling the complexity of computing a Nash equilibrium). In addition, he co-developed the first optimal well-shaped Delaunay mesh generation algorithms for arbitrary three-dimensional domains, settled the Rousseeuw-Hubert regression-depth conjecture in robust statistics, and resolved two long-standing complexity-theoretical questions regarding the Sprague-Grundy theorem in combinatorial game theory. For his industry work with Xerox, NASA, Intel, IBM, Akamai, and Microsoft, he received fifteen patents in areas including compiler optimization, Internet technology, and social networks, and was recently named a fellow of the National Academy of Inventors.
孙贺He Sun
中国科学院深圳先进技术研究院Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences
演讲时间：6 月 19 日 10:30-11:00Talk time: June 19, 10:30-11:00
报告题目: Dynamic Spectral Clustering with Provable Approximation Guarantee
摘要
Spectral clustering is one of the most fundamental clustering algorithms in machine learning and has comprehensive applications in many fields of computer science. In this talk, I will introduce the basics of spectral clustering, starting with its roots in spectral graph theory and its connection to eigenvalues and eigenvectors of graph Laplacians. I will present a spectral clustering algorithm in dynamic settings and discuss techniques for analyzing its performance. Several open problems will be discussed at the end of the talk. This is based on joint work with Steinar Laenen from Google Zurich.
Professor He Sun is the Director of Center for Algorithms and Learning Theory, Shenzhen Institutes of Advanced Technology, CAS, and the Associate Director of the State Key Laboratory of Biomedical Imaging Science and System. He received his Ph.D. from Fudan University in 2010 and worked at the MPI for Informatics, UC Berkeley, University of Bristol, and University of Edinburgh. He has been honored with many fellowships and awards, including the President's Medal of Fudan University (2004), Shanghai Outstanding Ph.D. Thesis Award (2010), Simons-Berkeley Research Fellowship (2014), and EPSRC Fellowship (2020). He has served as an area chair and PC member of leading international conferences including ICML (2024-2026), NeurIPS (2026), and STOC (2026).
Bakh M. KhoussainovBakh M. Khoussainov
电子科技大学University of Electronic Science and Technology of China
演讲时间：6 月 19 日 11:00-11:30Talk time: June 19, 11:00-11:30
报告题目: Deciding McNaughton and Muller games: Breaking through the 2^{O(|W| log |W|)} barrier
摘要
We present decision algorithms for regular games, focusing on Muller and McNaughton games. For McNaughton games, we remove the parameter-dependent logarithmic factor from the exponent of running times, breaking the log-barrier and distinguishing them from Rabin, colored Muller, and Streett games. This is achieved via a new technique for compressing attractor sequences. For Muller games, we give a polynomial-time algorithm for explicit representations that avoids reductions to other game classes or methods like Horn/Zielonka/McNaughton, with a clean combinatorial correctness proof. Both contributions introduce new methods advancing the theory of regular games. The work is joint with Dr. Zihui Liang.
Bakh M. Khoussainov is a professor of computer science at the University of Electronic Science and Technology of China in Chengdu and leads the Algorithm and Logic Lab in its computer science school. His research includes computable structures, automatic structures, games on graphs, mechanism design, and probability structures.
王子贺Zihe Wang
中国人民大学Renmin University of China
演讲时间：6 月 19 日 11:30-12:00Talk time: June 19, 11:30-12:00
报告题目: Second-Best Bilateral Trade is 1/2 Efficient
摘要
The landmark Myerson-Satterthwaite Theorem establishes a fundamental impossibility in bilateral trade: no Bayesian incentive-compatible mechanism can simultaneously achieve ex-post efficiency, individual rationality, and strong budget balance. We resolve a long-standing open question regarding the efficiency loss imposed by these constraints. Specifically, we prove that the Bayesian-optimal second-best mechanism always captures at least half of the first-best gains from trade, SB >= 0.5 * FB. This result is tight, definitively closing the gap between the previously best-known bounds of 0.317 and 0.736.
王子贺，中国人民大学预聘副教授。本科就读于清华大学计算机科学实验班，2016年在清华大学获博士学位，博士导师为唐平中和姚期智，毕业后在上海财经大学工作4年，后加入中国人民大学高瓴人工智能学院。研究兴趣为理论计算机与经济学的交叉学科，如博弈论、机制设计、算法设计等。
Zihe Wang is an assistant professor at Renmin University of China. He studied in the Computer Science Experimental Class at Tsinghua University and received his Ph.D. from Tsinghua University in 2016, advised by Pingzhong Tang and Andrew Chi-Chih Yao. After four years at Shanghai University of Finance and Economics, he joined the Gaoling School of Artificial Intelligence at Renmin University of China. His research interests lie at the intersection of theoretical computer science and economics, including game theory, mechanism design, and algorithm design.
邓小铁Xiaotie Deng
北京大学Peking University
演讲时间：6 月 19 日 14:00-15:00Talk time: June 19, 14:00-15:00
报告题目: How Would AI Establish Multiagent Economics? Keynote
Xiaotie Deng is Chair Professor of the Center on Frontiers of Computing Studies at Peking University and Director of the Center for Multi-agent Research at the Institute for Artificial Intelligence, Peking University. His research interests include algorithmic game theory, computational economics, blockchain, online algorithms, and parallel computing.
彭泱Yang Peng
卡内基梅隆大学Carnegie Mellon University
演讲时间：6 月 19 日 15:00-15:30Talk time: June 19, 15:00-15:30
报告题目: Has AI “Solved Programming Contests”? Some Thoughts on LLM Problem Solving
Yang (Richard) Peng is an associate professor in the School of Computer Science at Carnegie Mellon University. His research focuses on fast algorithms for fundamental computational problems, including graph algorithms, dynamic algorithms, linear algebraic algorithms, max-flow/min-cut algorithms, and efficient data structures.
黄志毅Zhiyi Huang
香港大学The University of Hong Kong
演讲时间：6 月 19 日 16:30-17:00Talk time: June 19, 16:30-17:00
报告题目: Calibeating Made Simple
摘要
We study calibeating, the problem of post-processing external forecasts online to minimize cumulative loss relative to an informativeness-based benchmark. Unlike prior work, which analyzed calibeating for specific losses using specialized arguments, we reduce calibeating to existing online learning techniques and obtain results for general proper losses. We show that calibeating is minimax-equivalent to regret minimization, recover the O(log T) rate for the Brier and log losses, obtain new optimal rates for mixable and bounded losses, and prove that multi-calibeating is minimax-equivalent to the combination of calibeating and the classical expert problem. We also obtain new bounds for achieving calibeating and calibration simultaneously for the Brier loss.
Zhiyi Huang is Professor and Head of Computer Science at the School of Computing and Data Science, the University of Hong Kong. His research broadly concerns algorithms, with a focus on the role of information and uncertainty in computation. His interests include algorithms for sequential decision-making under uncertainty, learning from different forms of information, incentivizing self-interested agents to share private information, and disclosing one type of information while keeping another confidential.
冯逸丁Yiding Feng
香港科技大学The Hong Kong University of Science and Technology
演讲时间：6 月 19 日 17:00-17:30Talk time: June 19, 17:00-17:30
报告题目: Strengthening Bulow-Klemperer-Style Results for Multi-Unit Auctions
摘要
The classic result of Bulow and Klemperer (1996) shows that in multi-unit auctions with m units and n≥m buyers whose values are sampled i.i.d. from a regular distribution, the revenue of the VCG auction with m additional buyers is at least as large as the optimal revenue. Unfortunately, for regular distributions, adding m additional buyers is sometimes indeed necessary, so the "competition complexity" of the VCG auction is m. We seek proving better competition complexity results in two dimensions. First, under stronger distributional assumptions, the competition complexity of VCG auction drops dramatically. In balanced markets (where m=n) with MHR distributions, it is sufficient to only add 0.4447n additional buyers to match the optimal revenue -- less than half the number that is necessary under regularity -- and this bound is asymptotically tight. We provide both exact finite-market results for small value of n, and closed-form asymptotic formulas for general market with any m≤n, and any target fraction of the optimal revenue. Second, we analyze a supply-limiting variant of VCG auction that caps the number of units sold in a prior-independent way. Whenever the goal is to achieve almost the optimal revenue, this mechanism strictly improves upon standard VCG auction, requiring significantly fewer additional buyers.
Yiding Feng is an Assistant Professor in the Department of Industrial Engineering and Decision Analytics at The Hong Kong University of Science and Technology (HKUST). Prior to joining HKUST, he was a Principal Researcher at the University of Chicago Booth School of Business and a Postdoctoral Researcher at Microsoft Research New England. He received his Ph.D. in Computer Science from Northwestern University in 2021 and his B.S. from the ACM Honors Class at Shanghai Jiao Tong University in 2016. His research interests lie at the intersection of operations research, economics and computation, and theoretical computer science. His work has been published in leading journals such as Management Science and Operations Research, as well as top theoretical computer science and economics conferences including STOC, FOCS, SODA, EC, ITCS, and WINE.
张涵瑞Hanrui Zhang
香港中文大学The Chinese University of Hong Kong
演讲时间：6 月 19 日 17:30-18:00Talk time: June 19, 17:30-18:00
报告题目: The Limits of Price Discrimination with a Bayesian Seller
摘要
We study the limits of third-degree price discrimination when the production cost is Bayesian and private to the seller, generalizing the seminal work of Bergemann, Brooks and Morris (AER, 2015). The rough setup is the following: A monopoly seller sets different prices for buyers in different "segments" of the market so as to maximize seller surplus. Different ways in which the aggregate market is decomposed into segments lead to different welfare outcomes, i.e., seller surplus and buyer surplus pairs. When the production cost is Bayesian, the region of achievable welfare outcomes can exhibit complex shapes beyond the clean characterization by Bergemann, Brooks and Morris for the case with a fixed cost. We show that with a Bayesian cost, this region coincides with a proper projection of a polytope defined by a polynomial number of linear constraints, the essential ones of which correspond to flow conservation in a "discounted" flow network. As a result, we give a polynomial-time algorithm that computes optimal market segmentations in terms of any linear combination of the seller surplus and the buyer surplus. En route, we establish the following structural property: Any market can be written as a convex combination of "extremal markets" in a way preserving the seller surplus and the buyer surplus. These extremal markets are piecewise equal-surplus with respect to different possible costs, generalizing a similar notion introduced by Bergemann, Brooks and Morris when the cost is fixed.
Hanrui Zhang is an Assistant Professor of Computer Science and Engineering at the Chinese University of Hong Kong. He obtained his Ph.D. from CMU and his bachelor's degree from Tsinghua University. He was a postdoctoral fellow at SLMath and worked at Google Research several times in different capacities. His work covers topics such as algorithmic mechanism design and information design, online advertising and autobidding, and strategic aspects of machine learning.
蔡进一Jin-Yi Cai
威斯康星大学麦迪逊分校University of Wisconsin-Madison
演讲时间：6 月 20 日 09:00-10:00Talk time: June 20, 09:00-10:00
报告题目: Keynote
Jin-Yi Cai is the Juris Hartmanis Professor in Computer Science (WARF) and Rajiv & Ritu Batra Chair at the University of Wisconsin-Madison. He received his Ph.D. from Cornell University in 1986 and works in computational complexity theory, especially the classification program for counting problems.
陈翌佳Yijia Chen
上海交通大学Shanghai Jiao Tong University
演讲时间：6 月 20 日 10:20-10:50Talk time: June 20, 10:20-10:50
报告题目: Homomorphism Counts on CFI-graphs
摘要
CFI graphs, named after Cai, Fürer, and Immerman, are central to the study of graph isomorphism testing and first-order logic with counting. Although introduced more than three decades ago, they continue to find new applications across computer science. This talk discusses recent results that shed new light on CFI graphs through the lens of homomorphism counts. Among other consequences, these results yield a new proof that the minimum dimension of a Weisfeiler-Leman algorithm that distinguishes two CFI graphs is precisely the treewidth of the base graphs.
Yijia Chen is a professor of computer science at Shanghai Jiao Tong University. He received his Ph.D. in computer science from Shanghai Jiao Tong University and his Ph.D. in mathematics from the University of Freiburg. His research focuses on logic in computer science, computational complexity, and algorithmic graph theory. He serves on the editorial boards of Logic Methods in Computer Science and Theory of Computing Systems.
邵帅Shuai Shao
中国科学技术大学University of Science and Technology of China
演讲时间：6 月 20 日 10:50-11:20Talk time: June 20, 10:50-11:20
报告题目: An LP algorithm for counting Eulerian orientations through the lens of polymorphism
邵帅，中国科学技术大学计算机学院特任教授、博士生导师。2014年本科毕业于中国科大少年班学院华罗庚班，2020年博士毕业于威斯康星大学麦迪逊分校计算机系，之后分别在牛津大学和爱丁堡大学从事博士后工作。主要研究方向为理论计算机科学及其与统计物理、量子理论的交叉方向。
Shuai Shao is a pre-tenured professor and doctoral advisor in the School of Computer Science and Technology at the University of Science and Technology of China. He received his Ph.D. from the University of Wisconsin-Madison in 2020 and later worked as a postdoctoral researcher at Oxford and Edinburgh. His research lies in theoretical computer science and its connections with statistical physics and quantum theory.
夏盟佶Mingji Xia
中国科学院软件研究所Institute of Software, Chinese Academy of Sciences
演讲时间：6 月 20 日 11:20-11:50Talk time: June 20, 11:20-11:50
报告题目: The SU(2) Group Classification Scheme for the Final Boolean Dichotomy Theorem
摘要
In the CSP dichotomy theorem, the NP-hardness of 3SAT and the polynomial-time tractability of Horn-SAT arise from the essential properties of the constraint function set F when it consists of 3-ary disjunctive functions and Horn functions, respectively. A broader class, Rtw-Positively-CSP, is needed to accommodate the tractable maximum matching problem.
In the counting version, the dichotomy theorem for Boolean variables has undergone three decades of development, and it is still a long and winding road toward the dichotomy theorem for #Rtw-Positively-CSP, also known as the Holant problem. The latest dichotomy theorem resolves the case where the constraint function set F contains odd-ary functions. From a coarse perspective, the only remaining case is when F consists entirely of even-ary functions.
Assume F is finite and the functions take values in an algebraic extension field of R. From a refined algebraic perspective, it can be shown that the binary functions realizable by #F necessarily form a finite subgroup of SL(2, C).
Since every finite group has a unitary representation, the classification of SU(2) yields five major classes. According to the characteristics of counting complexity, these are further subdivided into nine classes. Based on two mutually exclusive conditions - whether every quaternary function is decomposable, or there exists a genuinely indecomposable quaternary function - the nine classes are split into upper nine classes and lower nine classes. The lower nine need to solve quaternary base, which can serve as the base case for induction; the upper nine need to determine whether functions of arbitrary arity can preserve the non-<T> property, so that induction can reduce the arity down to four.
For the upper nine, there may also be a "clever bypass" method, named realnumberizing, to the known dichotomy theorems: when every quaternary function is decomposable, analogous to the realnumberizing process of the #EO dichotomy theorem, one can magically bulid an equivalent reduction from the complex-valued problems to some real-valued problems, and then invoke the dichotomy theorem for Real-Holant.
Mingji Xia received his Ph.D. from the Institute of Software, Chinese Academy of Sciences in 2008, and became a doctoral supervisor in 2019. Ten years ago, on the eve of the founding of ITCS, he collaborated with Jin-Yi Cai, Pinyan Lu, and Zhiguo Fu on the dichotomy theorems for #CSP² and the six-vertex model. In the following years, he marveled at the dichotomy theorems on classes such as ARS-EO and Real-Holant achieved by Shao Shuai et al. More recently, he collaborated with his Ph.D. students Boning Meng and Juqiu Wang on the dichotomy theorems for #EO and Holant-odd. This group classification scheme, derived from analyzing and summarizing the coverage of those brilliant dichotomy theorems, is reported here for the first time in celebration of the 10th anniversary of ITCS.
付治国Zhiguo Fu
东北师范大学Northeast Normal University
演讲时间：6 月 20 日 14:00-14:30Talk time: June 20, 14:00-14:30
报告题目: The Computational Complexity Dichotomy of Holant Problems on 4-regular Graphs
付治国，东北师范大学信息科学与技术学院教授、副院长、博士生导师。2009年博士毕业于吉林大学数学学院，曾在美国威斯康星大学麦迪逊分校从事博士后研究。主要研究领域为计数问题的精确求解和近似求解的计算复杂性分类问题,机器学习的理论基础等。
Zhiguo Fu is a professor, vice dean, and doctoral advisor in the School of Information Science and Technology at Northeast Normal University. He received his Ph.D. from Jilin University in 2009 and conducted postdoctoral research at the University of Wisconsin-Madison. His research includes holographic algorithms, complexity classifications of counting problems, approximate counting algorithms, and generalization analysis in deep learning.
张驰豪Chihao Zhang
上海交通大学Shanghai Jiao Tong University
演讲时间：6 月 20 日 14:30-15:00Talk time: June 20, 14:30-15:00
报告题目: Discrete Optimal Transport and Its Applications in Sampling
Chihao Zhang is an associate professor at the John Hopcroft Center for Computer Science, Shanghai Jiao Tong University. He works in the area of theoretical computer science.
张梦晓Mengxiao Zhang
爱荷华大学University of Iowa
演讲时间：6 月 20 日 16:00-16:30Talk time: June 20, 16:00-16:30
报告题目: Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
摘要
Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, Fiegel et al. [2025] show a separation between average-iterate and last-iterate convergence in duality gap. However, in many practical settings, the players observe not only their loss but also the opponent's action. We show that t^{-1/2} last-iterate convergence is achievable with high probability in this setting via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier regularized game. We identify obstacles preventing standard multi-armed bandit analysis from generalizing to games and develop a new analysis to overcome them. Experiments confirm faster convergence than baselines and prior methods that do not exploit opponent-action feedback.
Mengxiao Zhang is an assistant professor in the Department of Business Analytics at the University of Iowa. He received his Ph.D. in computer science from the University of Southern California, advised by Haipeng Luo. His research focuses on the design of robust and adaptive machine learning algorithms with strong theoretical guarantees, with an emphasis on sequential learning problems, including online learning, bandit problems, game theory, and applications in operations research and revenue management.
Kaito FujiiKaito Fujii
京都大学Kyoto University
演讲时间：6 月 20 日 16:30-17:00Talk time: June 20, 16:30-17:00
报告题目: Bayes Correlated Equilibria and No-Regret Dynamics
摘要
In this talk, I will examine regret notions and the computational tractability of correlated equilibria in Bayesian games. Unlike the complete-information case, the Bayesian setting admits several natural yet non-equivalent correlated-equilibrium concepts (Forges, 1993). I will mainly focus on communication equilibrium (Myerson, 1982), which combines truth-telling incentive constraints from mechanism design and obedience incentive constraints from correlated equilibria, and its associated notion of untruthful swap regret. We present an efficient algorithm for minimizing untruthful swap regret, and also provide an information-theoretic lower bound. Furthermore, I will discuss the price of anarchy and the price of stability for these correlated-equilibrium concepts.
Kaito Fujii is a senior lecturer at Kyoto University. Previously, he was an assistant professor at the National Institute of Informatics and SOKENDAI. He received his Ph.D. from the University of Tokyo in 2020. His research interests lie at the intersection of combinatorial optimization, machine learning, and game theory, including submodular maximization, active learning, optimal stopping theory, online learning, and correlated equilibria.
Ioannis PanageasIoannis Panageas
加利福尼亚大学欧文分校University of California, Irvine
演讲时间：6 月 20 日 17:00-17:30Talk time: June 20, 17:00-17:30
报告题目: The Computational Landscape of Avoiding Saddle Points: From Dynamics to Computational Complexity
摘要
The escape from undesirable strict saddle points has been a central challenge in non-convex optimization for over a decade, particularly within the context of training modern machine learning models. While earlier research focused on establishing that first-order methods almost always avoid such points, mainly in unconstrained settings, the exact computational complexity of finding second-order stationary points (SOSPs) has remained a nuanced problem. This talk bridges the gap between the dynamics of local search and the formal complexity classes of $TFNP$. We present recent results showing that finding an $\epsilon$-SOSP over polytope constraints is $PLS$-complete. This result is surprising, as it holds even for remarkably simple domains, such as the two-dimensional unit square $[0,1]^2$. Crucially, we establish a fundamental barrier: unless $PLS \subseteq PPAD$, there can be no deterministic, iterative algorithm with a computationally efficient, continuous update rule for finding approximate SOSPs in constrained settings. This stands in stark contrast to finding first-order KKT points, a task known to be $CLS$-complete and one where gradient descent is guaranteed to succeed. We will discuss the implications of this “discreteness” in the complexity of second-order optimization and what it means for the future of continuous local search algorithms.
Ioannis Panageas is an Assistant Professor in the Department of Computer Science at the Donald Bren School of Information and Computer Sciences, University of California, Irvine, and the director of the GOALLab. He is affiliated with the Center for Algorithms and Theory of Computation, the Center for Machine Learning and Intelligent Systems, and the Algorithms, Combinatorics and Optimization Center. Before joining UCI, he was an Assistant Professor at the Singapore University of Technology and Design and a MIT Postdoctoral Fellow. He received his Ph.D. in Algorithms, Combinatorics, and Optimization from Georgia Tech.
Sai Ganesh NagarajanSai Ganesh Nagarajan
南丹麦大学University of Southern Denmark
演讲时间：6 月 20 日 17:30-18:00Talk time: June 20, 17:30-18:00
报告题目: The Complexity of Two-Team Polymatrix Games with Independent Adversaries
摘要
Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are known to be efficiently computable. Towards understanding the limits of tractability in polymatrix games, we study the computation of Nash equilibria in such games where each pair of players plays either a zero-sum or a coordination game. A setting that is particularly interesting is where players can be grouped into a small number of teams of identical interest [Von Stengel and Koller 1997]. While the three-team version of the problem is known to be PPAD-complete, the complexity for two teams has remained open [Cai and Daskalakis 2011]. In this talk, we show that the two-team version is CLS-hard, by proving the hardness of finding any stationary point in the simplest type of non-convex-concave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions. Finally, we discuss some algorithms for a restricted version of this problem, namely a team with non-interacting adversaries.
Sai Ganesh Nagarajan is a tenure-track Assistant Professor in the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. Before joining SDU, he was a postdoctoral researcher and research area lead of the learning group at the Zuse Institute Berlin, and earlier a postdoctoral researcher at EPFL. He completed his Ph.D. at the Singapore University of Technology and Design. His research focuses on the foundations of multiagent AI, learning dynamics, min-max optimization, and applications of game theory and min-max optimization to AI safety.
Nick HarveyNick Harvey
不列颠哥伦比亚大学University of British Columbia
演讲时间：6 月 21 日 09:00-10:00Talk time: June 21, 09:00-10:00
报告题目: Keynote
Nick Harvey is a full professor in the Department of Computer Science at the University of British Columbia, an associate member of UBC's Department of Mathematics, and director of the Mathematics of Information, Learning and Data research cluster. His research interests include theory of machine learning, randomized algorithms, and convex optimization.
刘正阳Zhengyang Liu
北京理工大学Beijing Institute of Technology
演讲时间：6 月 21 日 10:20-10:50Talk time: June 21, 10:20-10:50
报告题目: Computing Exact Second-Price Pacing Equilibria with Few Agents or Goods
摘要
Second-price pacing equilibria (SPPE) play a foundational role in modern online advertising auctions. However, computing or even approximating SPPE is known to be PPAD-hard in general. In this talk, we present a unified algorithmic framework that overcomes this computational barrier, yielding polynomial-time algorithms for exactly computing SPPEs in two natural, restricted market settings: instances with a constant number of buyers or a constant number of goods. Our algorithms heavily rely on a cell-decomposition approach. This is joint work with Yonglei Yan, Yiyang Huang, and Zihe Wang.
刘正阳，北京理工大学计算机学院长聘副教授、博士生导师。主要研究方向为算法博弈论，在相关领域国际顶级期刊和会议发表论文20余篇。主持国家自然科学基金青年项目、面上项目。现任中国运筹学会博弈论分会理事，中国计算机学会理论计算机科学专委会、计算经济学专委会执行委员。
Zhengyang Liu is a tenured associate professor and doctoral advisor at the School of Computer Science, Beijing Institute of Technology. His research focuses on algorithmic game theory. He has published more than 20 papers in leading journals and conferences, led National Natural Science Foundation of China projects, and serves in several professional committees in game theory, theoretical computer science, and computational economics.
曹乃仁Nairen Cao
纽约大学New York University
演讲时间：6 月 21 日 10:50-11:20Talk time: June 21, 10:50-11:20
报告题目: Bounding the Fragmentation of B-Trees Subject to Batched Insertions
摘要
B-trees are fundamental in database systems, but repeated insertions can leave their leaves underfull, causing internal fragmentation. A classical result of Yao shows that evenly splitting leaves under uniformly random single-key insertions gives about ln2≈69% average space utilization. We study a more realistic batched model, where each update inserts r consecutive keys at a uniformly random position. We show that batched insertions lead to surprisingly non-monotone behavior: even splitting can work well for some batch sizes but drop to 50% utilization for others. We analyze several simple local splitting strategies and show that for every fixed batch size r, one of these strategies guarantees space utilization bounded away from 50%.
Nairen Cao is a Faculty Fellow at NYU Tandon School of Engineering working in theoretical computer science. His research lies in algorithm design and analysis, with a particular focus on parallel and distributed algorithms for graph problems and combinatorial optimization. He has worked on topics including shortest paths, correlation clustering, and related problems in modern parallel models. His papers have appeared in venues such as STOC, SODA, SPAA, PODC, ESA, and ICALP, and his work received Outstanding Paper Awards at SPAA in 2022 and 2023.
Jannik PetersJannik Peters
上海财经大学Shanghai University of Finance and Economics
演讲时间：6 月 21 日 11:20-11:50Talk time: June 21, 11:20-11:50
报告题目: An Axiomatic Analysis of Proportionality Notions
摘要
Even though proportional representation is a fundamental goal in multiwinner voting and a plethora of proportionality notions has been introduced, the normative justifications for choosing one notion over another remain poorly understood. We address this by introducing the axiomatic study of proportionality notions in the approval-based multiwinner voting setting. That is, we define axioms, or desirable properties, that "good" proportionality notions should possess. Using these axioms, we then provide axiomatic characterizations of two prominent recently introduced notions: PJR+ and EJR+.
Jannik Peters joined Shanghai University of Finance and Economics as an assistant professor in early 2026. Before this, he was a postdoctoral researcher at the National University of Singapore and received his Ph.D. from TU Berlin in Germany. His work is on collective decision-making and computational social choice. In particular, he works on formalizing what makes decisions representative.
