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

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

• 批准号: 2302174
• 负责人: Greta Panova
• 金额: $ 27.75万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2302174&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.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的代数类似物，分别。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

ON THE CROSS-PRODUCT CONJECTURE FOR THE NUMBER OF LINEAR EXTENSIONS

关于线性延拓数的叉积猜想

• DOI: 10.4153/s0008414x24000087
• 发表时间: 2024
• 期刊: Canadian Journal of Mathematics
• 作者: CHAN, SWEE HONG;PAK, IGOR;PANOVA, GRETA
• 通讯作者: PANOVA, GRETA