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

AF：小：结构和算法之间的多态网关：超越 CSP 二分法

• 批准号: 1908125
• 负责人: Venkatesan Guruswami
• 金额: $ 40万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908125&HistoricalAwards=false
• 关键词: AF; Small; Polymorphic; Gateway; between

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.

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

项目成果

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems

结合基本线性规划和仿射松弛来解决承诺约束满足问题的威力

• DOI: 10.1137/20m1312745
• 发表时间: 2020-01
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Brakensiek, Joshua;Guruswami, Venkatesan;Wrochna, Marcin;Živný, Stanislav
• 通讯作者: Živný, Stanislav

Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

通过低灵敏度多态性获得彩虹着色硬度

• DOI: 10.1137/19m127731x
• 发表时间: 2020-01
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Guruswami, Venkatesan;Sandeep, Sai
• 通讯作者: Sandeep, Sai

The Quest for Strong Inapproximability Results with Perfect Completeness

追求完美完整性的强不可近似性结果

• DOI: 10.1145/3459668
• 发表时间: 2021-08
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Brakensiek, Joshua;Guruswami, Venkatesan
• 通讯作者: Guruswami, Venkatesan