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

这个项目的目的是研究围绕某些数字和多项式的各种问题，这些数字和多项式描述了代数和几何中的基本对称性。尽管它们的基本性质和长达百年的历史，这些物体在很大程度上是神秘的，仍然是代数组合学最近发展的核心。主要目标是了解它们的计算性质和行为，这将对许多领域产生深远影响。在一个方向上，研究人员的目标是利用计算复杂性理论的框架来解释为什么这些物体如此难以理解。另一方面，他们的目标是利用这些对象和量来确定某些基本多项式的计算复杂性。具体地说，该项目位于计算复杂性和代数组合学的交叉点上。本课程的目的是增进对几个结构常数计算的渐近性和复杂性的理解，这些结构常数包括Kronecker系数、Plethysm系数和Schubert系数，这些系数构成了代数组合学中的一些主要公开问题。它们的计算复杂性将解释为什么这些结构常数在经过数十年的研究后仍然如此难以捉摸，并将暗示将会有什么样的解决方案。了解它们的行为和渐近性可以给几何复杂性理论中的基本问题和多项式带来新的下界，如矩阵乘法和计算永久数的复杂性。从广义上看，该项目致力于分离计算复杂性类别VP和VNP，它们分别代表著名的复杂性类别P和NP的代数类似物。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.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.