Andrew Chi-Chih Yao (Tsinghua University, China)
Title
TBA
Abstract
TBA
Andrei Bulatov (Simon Fraser University, Canada)
Biography
Dr.Bulatov received his Ph.D. in 1995 from the Ural State University in Ekaterinburg, Russia. His early research area was universal algebra and clone theory. When connections between universal algebra and computer science had been discovered, he pioneered the so-called algebraic approach to the Constraint Satisfaction Problem and related fields. In 2000 Dr.Bulatov moved, first, to the University of Oxford, and then to Simon Fraser University in Canada, where he works till now. Dr.Bulatov is an expert on applications of algebraic methods in computer science. He is a recipient of the 2021 Godel Prize and 2024 Frontiers of Science Award from the International Congress on Basic sciences.
Title
The Complexity of CSP-Based Ideal Membership Problems
Abstract
In this talk we consider the Ideal Membership Problem (IMP for short), in which we are given polynomials f_0,f_1,...,f_k and the question is to decide whether f_0 belongs to the ideal generated by f_1,...,f_k. In the more stringent version the task is also to find a proof of this fact. The IMP underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares (SOS). In such applications the IMP usually involves so-called combinatorial ideals that arise from a variety of discrete combinatorial problems. This restriction makes the IMP significantly easier and in some cases allows for an efficient solution algorithm. The first part of this talk follows the work of Mastrolilli [SODA 2019] who initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form CSP(G), that is, CSPs in which the type of constraints is limited to relations from a set G. We show that many CSP techniques can be translated to IMPs thus allowing us to significantly improve the methods of studying the complexity of the IMP. In particular, we use them to prove a general necessary condition for the tractability of the IMP, and three sufficient ones. The sufficient conditions include IMPs arising from systems of linear equations over GF(p), p prime, and also some conditions defined through similar conditions. Our work has several consequences and applications. We mention one of them - a variation of the IMP and based on this propose a unified framework, different from the celebrated Buchberger's algorithm, to construct a bounded degree Groebner Basis. Our algorithm, combined with CSP techniques, leads to polynomial-time construction of Groebner Basis for many combinatorial problems.
Saket Saurabh (Institute of Mathematical Sciences, India; University of Bergen, Norway)
Title
TBA
Abstract
TBA
Ding-Zhu Du (University of Texas at Dallas, USA)
Biography
Dingzhu Du received his Master’s degree in 1982 from the Chinese Academy of Sciences and Ph.D. in 1985 from the University of California at Santa Barbara. His research areas include optimization theory and mathematical foundation of computer science. As a researcher in mathematics and theoretical computer science, he has held positions with MSRI (Berkeley), MIT, Chinese Academy of Sciences, Princeton University, University of Minnesota, and NSF of USA; he is now a professor at the University of Texas at Dallas. He has spent leaves of absence at various institutions, such as Korea University, City University of Hong Kong, and Xi’an Jiaotong University. He has published over 260 journal papers and 10 books and has served on editorial boards of 15 international journals. He was granted the Natural Science Prize (First Class) of the Chinese Academy of Sciences in 1992, the National Natural Science Prize (Second Class) of China in 1993, and the CSTS award of INFORMS in 1998.
Title
Approximation of Local Optimum: Nonsubmodular Optimization
Abstract
In the study of approximation algorithms, the classic measure for approximation performance is the ratio of objective function values between the approximation solution and the optimal solution on the same input, that is, the comparison of the approximation solution with the optimal solution. Usually, the optimal solution used is optimal for the entire feasible region, called the global optimal solution. Recent, it gets attention on comparing the approximation solution with the local optimal optimal solution due to the following: (a) In developments of computer technology, there are many nonsubmodular optimization problems raised. (b) In the study of nonsubmodular optimizations, a new performance measure has to be established based on comparing approximation solution and local optimal solution. In this talk, we introduce new developments in this research direction.
Shang-Hua Teng (University of Southern California, USA)
Biography
Shang-Hua Teng is a University Professor and Seely G. Mudd Professor of Computer Science and Mathematics at USC. He is a fellow of SIAM, ACM, and 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 Simons Investigator to pursue long-term curiosity-driven fundamental research. He also received the 2009 Fulkerson Prize, 2023 Science & Technology Award for Overseas Chinese from the China Computer Federation, 2022 ACM SIGecom Test of Time Award (for settling the complexity of computing a Nash equilibrium), 2021 ACM STOC Test of Time Award (for smoothed analysis), 2020 Phi Kappa Phi Faculty Recognition Award (2020) for his book Scalable Algorithms for Data and Network Analysis, 2011 ACM STOC Best Paper Award (for improving maximum-flow minimum-cut algorithms). In addition, he and collaborators 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.
Title
P+P ≧ PSPACE: Deep Logic, Strategic Losing, and Game Secrets
Abstract
A combinatorial game is defined by a succinct ruleset, specifying game positions, and the set of feasible options each player can move every position to. 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 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 to 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 settled 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 to a famous Chinese idiom, in honor of Chengdu's hero, 诸葛亮 (Zhu Ge Liang), in this city rich in history and culture.
Joint work with Kyle Burke (Florida Southern College) and Matt Ferland (Dickinson College).