权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
2228287
负责人：
Venkatesan Guruswami
金额：
$ 40万
依托单位：
University of California-Berkeley
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-03-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2228287&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 courses.As一个具体的推力，该项目将调查的复杂性承诺版本的CSP，在那里的算法是允许找到一个分配满足放松版本的约束定义的CSP。promise CSP框架非常通用，并捕获了各种各样的问题，最值得注意的是近似（超）图着色和变体。虽然CSP的多态性在组合下是封闭的（因此可以从单个非平凡多态性构建丰富的家族），但多态性在承诺设置中内在地失去了组合下的这种封闭性。因此，对承诺CSP的研究在算法和硬度方面都需要有重大的新想法。特别是，该研究将结合两种非常成功的方法，即CSP的代数方法和基于概率可检验证明（PCP）的近似理论。在算法方面，该研究将在存在足够丰富的多态性家族的情况下发现新算法。该项目还将在更广泛的背景下研究结构和算法之间的多态网关，包括快速指数算法，其中部分多态性控制NP-hard CSP算法的（指数）运行时间。该研究将与各种主题建立新的联系，包括优化，固定参数易处理性，细粒度复杂性，判断聚合，PCP，极值组合学和通用代数。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。