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.

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