Computational problems are ubiquitous and exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. One of the broad intellectual challenges driving research in the theory of computation is the following: What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Algorithms are everywhere in today's world, and understanding their power and limitations is important both for foundational reasons as well as the myriad applications that efficient algorithms empower. Given the vast landscape of problems and possible clever algorithms to solve them, it is simplisic to hope to explain the underpinnings of the easiness/hardness of all problems with a single theory. However, recent progress has led to elegant theories that fully explain the computational complexity of rich classes of problems, notably constraint satisfaction problems (CSPs) and their variants. In this setting, an efficient algorithm exists precisely when there are non-trivial operations called polymorphisms under which the solution space is closed (this can be interpreted as a discrete analog of convexity that is typically at the heart of tractability of continuous optimization problems). Inspired by the success story for constraint satisfaction, the project will investigate the existence of polymorphic principles in broader contexts --- namely, whether "interesting" ways to combine solutions to get new solutions lead to efficient algorithms. The project will enable a cross-fertilization of ideas between the approximation algorithms and optimization literature and the powerful algebraic methods used to study CSPs, and foster enhanced collaborations between these research communities. Due to its balanced focus on exploratory directions and concrete problems, the project is well-suited for investigation by students, and will actively engage and train graduate as well as undergraduate students. The accompanying educational plan will distill suitable segments of the interplay between polymorphisms and algorithms for inclusion in the theory CS curriculum at various levels.
As a specific thrust, the project will investigate the complexity of promise versions of CSPs, where the algorithm is allowed to find an assignment satisfying relaxed versions of the constraints defining the CSP. The promise CSP framework is very general and captures a rich variety of problems, most notably approximate (hyper)-graph coloring and variants. While polymorphisms of CSPs are closed under composition (and therefore a rich family can be built from a single non-trivial polymorphism), polymorphisms inherently lose this closure under composition in the promise setting. As a result, the study of promise CSPs calls for significant new ideas on both the algorithms and hardness sides. In particular, the research will undertake a combination of two highly successful methodologies, the algebraic approach for CSPs and the probabilistically checkable proofs (PCP) based theory for approximation. On the algorithmic front, the research will uncover new algorithms in the presence of rich enough families of polymorphisms. The project will also investigate polymorphic gateways between structure and algorithms in broader contexts, including in fast exponential algorithms where partial polymorphisms govern the (exponential) runtime of algorithms for NP-hard CSPs. The research will forge new connections with diverse topics including optimization, fixed-parameter tractability, fine-grained complexity, judgement aggregation, PCP, extremal combinatorics, and universal algebra.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
