AF: Small: The Polymorphic Gateway between Structure and Algorithms: Beyond CSP Dichotomy

计算问题无处不在，在解决问题的速度和效率方面表现出各种不同的行为。推动计算理论研究的一个广泛的智力挑战如下：计算问题中的什么基本数学结构(或缺乏)会导致有效的算法来解决它(或决定它的难解性)？算法在当今世界无处不在，了解它们的能力和局限性是很重要的，这既是因为基础原因，也是因为高效算法所支持的无数应用程序。鉴于问题的广袤图景和可能的智能算法来解决它们，希望用一个单一的理论来解释所有问题的难易程度的基础是简单的。然而，最近的进展导致了优雅的理论，完全解释了丰富的问题类别的计算复杂性，特别是约束满足问题(CSP)及其变体。在这种情况下，当存在称为多态的非平凡操作时，就存在有效的算法，在这些操作下，解空间是封闭的(这可以被解释为凸性的离散模拟，其通常是连续优化问题的可处理性的核心)。受约束满足的成功案例的启发，该项目将在更广泛的上下文中调查多态原则的存在-即，组合解决方案以获得新解决方案的“有趣”方法是否会导致高效的算法。该项目将使近似算法和优化文献以及用于研究CSP的强大代数方法之间的思想交叉滋养，并促进这些研究社区之间的加强合作。由于其对探索方向和具体问题的平衡关注，该项目非常适合学生的调查，并将积极参与和培养研究生和本科生。随附的教育计划将提炼多态和算法之间相互作用的适当部分，以包括在不同级别的理论CS课程中。作为一个具体的主题，该项目将调查CSP承诺版本的复杂性，其中该算法被允许找到满足定义CSP的约束的放宽版本的作业。Promise CSP框架非常通用，并捕获了大量的问题，最显著的是近似(超)图着色和变体。虽然CSP的多态在组合下是封闭的(因此可以从单个非平凡的多态建立一个丰富的家族)，但在Promise环境中的组合下，多态本质上会失去这个闭包。因此，对Promise CSPs的研究需要在算法和难度方面都有重要的新想法。特别是，这项研究将结合两种非常成功的方法，即CSP的代数方法和基于概率可检验证明(PCP)的近似理论。在算法方面，这项研究将在存在足够丰富的多态家族的情况下发现新的算法。该项目还将在更广泛的背景下研究结构和算法之间的多态网关，包括在快速指数算法中，其中部分多态控制NP-Hard CSP算法的(指数)运行时间。这项研究将与不同的主题建立新的联系，包括优化、固定参数可处理性、细粒度复杂性、判断聚合、PCP、极值组合学和通用代数。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.