Collaborative Research: AF: Small: Combinatorial Complexity Problems

计算复杂性描述了需要什么样的计算资源，如时间、精力、空间和能量，来解决来自现实世界活动的具有挑战性的数学问题，如设计飞机、分析DNA证据或破解密码。这个项目应用了组合学和代数的最新前沿工作，以更清楚地确定哪些问题是棘手的（在太多的计算资源被浪费在试图解决它们之前）。这一点很重要，因为知道一个问题很难通过计算来解决，可以用在不同的方向上，比如创建更难破解的代码。组合学是一门古老的计算复杂数学对象的艺术，是早期数字计算机发展的摇篮。代数在这里指的是对某些对称性的研究，这些对称性最近被发现在复杂性理论中很重要。从技术上讲，本项目从代数组合学的角度探讨几何复杂性理论，以进一步阐明VP与VNP问题的可行方法。具体来说，部分工作将致力于计算复杂性，计算某些杨表和计算相关的常数和多项式在代数组合学和代数复杂性，分别。这些对象和数量虽然在上世纪初被引入，但至今仍未得到深入的了解。然而，它们最近从各个方向获得了健康的进展。理解它们的计算性质将澄清代数组合学中寻找自然对应（双射）的一些著名问题的可行性，并为它们的研究铺平一条新的途径，从而导致代数复杂性的更好的下界。这些目标和数量包括理解克罗内克系数（一个80年前的问题），以及有效地计算Kostka和littlewood - richardson系数。虽然不存在这些系数的封闭形式公式，但它们的渐近性可以导致几何复杂性理论中目前无法达到的新下界。具体地说，区分像VP和VNP这样的算术复杂度类归结为在仿射变换下区分它们的泛多项式（例如行列式与永久多项式），最终转化为涉及上述数量的表示论多重性之间的不等式。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computational complexity characterizes what kinds of computational resources,such as time, effort, space and energy, are needed to solve challenging mathematical problems derived from real-worldactivities, such as designingaircraft, analyzing DNA evidence, or breaking a secret code.This project applies recent cutting-edge work from combinatorics andalgebra to more clearly determine which problems are intractable (beforetoo many computational resources are wasted trying to solve them). This is important because,knowing that a problem is hard to solve computationally can beused in a different direction, such as creating codes that are harder tobreak. Combinatorics is the ancient art of counting complicated mathematicalobjects, and was the cradle for the development of early digital computers.Algebra here refers to the study of certain symmetries which have recentlybeen discovered to be important in complexity theory. More technically, this project approaches Geometric Complexity Theoryfrom the point of view of algebraic combinatorics to further clarifyfeasible approaches to the VP vs. VNP Problem.Specifically, part of the work will be devoted to the computational complexityof counting certain Young tableaux and computing related constantsand polynomials in Algebraic Combinatorics and Algebraic Complexity,respectively. These objects and quantities, while introduced in the beginningof last century, are still not deeply understood. However, they have recentlyenjoyed a healthy stream of advances fromvarious directions. Understanding their computational nature would clarify thefeasibility of some famous problems in Algebraic Combinatorics searching fornatural correspondences (bijections), and pave a new approach to their study,leading towards better lower bounds in algebraic complexity. These objects andquantities include understanding the Kronecker coefficients (an 80-year-oldproblem), and efficiently computing Kostka and Littlewood-Richardsoncoefficients. While no closed-form formulas for these coefficients exist,their asymptotics can lead to new lower bounds in Geometric Complexity Theorythat are currently out of reach.Specifically, distinguishing ArithmeticComplexity classes like VP and VNP boils down to distinguishing theiruniversal polynomials (e.g. determinant vs permanent) under affinetransformations, ultimately translating to inequalities between representationtheoretic multiplicities involving the quantities mentioned.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.