Andrew Chi-Chih Yao (Tsinghua University, China)
Title
Cryptography in the Age of AI, Bio and Quantum
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)
Biography
Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathematical Sciences (IMSc), Chennai. Saurabh spent two years (2007-2009) as a Postdoctoral Fellow at University of Bergen, Norway, and is now a professor at IMSc and at Department of Informatics at the University of Bergen. His main research interests are in graph algorithms, parameterized algorithms and complexity. He has written more than 300 articles, graduated more than 15 PhD students, and mentored around 10 post doctoral fellows. He is a co-author of two books: Parameterized Algorithms and Kernelization theory of parameterized preprocessing.
He is a SwarnaJayanti Fellow in Mathematical Sciences (2018), Fellow of Indian Academy of Sciences (2020), Academia Europaea (2020), and European Association for Theoretical Computer Science (EATCS, 2021). He received the inaugural ACM India Early Career Researcher Award in 2020, and Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 (Mathematical Science). He is also the recipient of an ERC starting grant and an ERC Consolidator Grants in parameterized algorithms. He was also named one of the ACM Distinguished Members in 2022.
Title
FPT Approximation Algorithms for Coverage and Satisfiability Problems
Abstract
The classical Max Coverage problem is defined as follows: Given a universe U of n elements, a family F of subsets of U, and an integer k, select k sets from F to maximize the number of elements covered. A greedy algorithm achieves a (1−1/e)-approximation in polynomial time, and this bound is tight assuming P≠NP. However, from the parameterized complexity viewpoint, Max Coverage is W[2]-hard when parameterized by k, and it is known to be hard to approximate within any constant factor in time f(k)⋅n^{o(k)}, assuming the Exponential Time Hypothesis (ETH). This rules out the possibility of constant-factor FPT approximation algorithms in general. To circumvent this hardness, we explore approximation schemes tailored to well-structured instances of the problem. An Efficient Polynomial-Time Approximation Scheme (EPAS) is an algorithm that, for every ε>0, returns a (1+ε)-approximate solution in time f(k,ε)⋅n^{O(1)}. A Parameterized Approximation Scheme (PAS) also returns a (1+ε)-approximate solution, but allows the dependence on ε in the exponent of n; that is, its running time is of the form f(k,ε)⋅n^{g(ε)} for some function g. In this talk, we list recent developments in designing EPASes and PASes for Max Coverage and its variants over well-structured set systems. These include families with bounded VC-dimension, bounded intersection complexity, or geometric and graph-based constraints. We describe algorithmic techniques that exploit such structures to obtain efficient approximation schemes. We also highlight connections to related problems in partial coverage, capacitated coverage, connected variants, and structurally restricted MaxSAT.
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).