Collaborative Research: AF: Small: Computational Complexity and Algebraic Combinatorics

合作研究：AF：小：计算复杂性和代数组合

• 批准号: 2302173
• 负责人: Igor Pak
• 金额: $ 32.25万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2302173&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Computational

This project aims to study a variety of problems centered around certain numbers and polynomials that describe fundamental symmetries in algebra and geometry. Despite their fundamental nature and century-long history, these objects have been largely mysterious and remain at the heart of recent developments in algebraic combinatorics. The main goal is to understand their computational nature and behavior, which would have far-reaching implications across many fields. In one direction, the researchers aim to explain, using the framework of Computational Complexity theory, why these objects are so difficult to understand. In another direction, they aim to use these objects and quantities to establish the computational complexity of certain fundamental polynomials.Specifically, the project lies in the intersection of Computational Complexity and Algebraic Combinatorics. The goal is to advance the understanding of the asymptotics and the complexity of computing several structure constants such as Kronecker, plethysm, and Schubert coefficients that comprise some of the main open problems in algebraic combinatorics. Their computational complexity would explain why these structure constants have remained so elusive despite decades of research and would hint at what solutions to expect. Understanding their behavior and asymptotics can lead to new lower bounds on fundamental problems and polynomials in Geometric Complexity Theory, such as the complexity of matrix multiplication and computing the permanent. Viewed broadly, the project works towards the separation of the computational complexity classes VP and VNP, which represent the algebraic analogues of the well-known complexity classes P and NP, respectively.Specifically, the project lies in the intersection of Computational Complexity and Algebraic Combinatorics. The goal is to advance understanding of the asymptotics and the complexity of computing several structure constants such as Kronecker, plethysm, and Schubert coefficients, which comprise some of the main open problems in the area of algebraic combinatorics. Their computational complexity would explain why these structure constants have remained so elusive despite decades of research and would hint towards what solutions to expect. Understanding their behavior and asymptotics can lead to new lower bounds on fundamental problems and polynomials in Geometric Complexity Theory such as the complexity of matrix multiplication, computing the permanent, etc. Viewed broadly, the project works towards separation of the computational complexity classes VP and VNP, which represent the algebraic analogues of the well-known complexity classes P and NP, respectively.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.

该项目旨在研究以描述代数和几何中基​​本对称性的某些数字和多项式为中心的各种问题。尽管它们具有基本的性质和长达一个世纪的历史，但这些物体在很大程度上仍然是神秘的，并且仍然是代数组合学最近发展的核心。主要目标是了解它们的计算性质和行为，这将对许多领域产生深远的影响。在一个方向上，研究人员旨在利用计算复杂性理论的框架来解释为什么这些对象如此难以理解。另一方面，他们的目标是使用这些对象和数量来确定某些基本多项式的计算复杂性。具体来说，该项目位于计算复杂性和代数组合学的交叉点。目标是加深对渐进性和计算多个结构常数（例如克罗内克、体积和舒伯特系数）的复杂性的理解，这些结构常数构成了代数组合学中的一些主要开放问题。它们的计算复杂性可以解释为什么尽管经过数十年的研究，这些结构常数仍然如此难以捉摸，并暗示了预期的解决方案。了解它们的行为和渐进性可以为几何复杂性理论中的基本问题和多项式带来新的下界，例如矩阵乘法和计算常量的复杂性。从广义上看，该项目致力于分离计算复杂性类别 VP 和 VNP，它们分别代表众所周知的复杂性类别 P 和 NP 的代数类似物。具体来说，该项目位于计算复杂性和代数组合学的交叉点。 目标是加深对渐进性和计算几个结构常数（例如克罗内克、体积和舒伯特系数）的复杂性的理解，这些常数构成了代数组合领域的一些主要开放问题。 它们的计算复杂性可以解释为什么尽管经过数十年的研究，这些结构常数仍然如此难以捉摸，并暗示了预期的解决方案。 了解它们的行为和渐进性可以为几何复杂性理论中的基本问题和多项式带来新的下界，例如矩阵乘法的复杂性、计算永久等。从广义上看，该项目致力于分离计算复杂性类别 VP 和 VNP ，分别代表著名的复杂性类别 P 和 NP 的代数类似物。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准。