权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Collaborative Research: AF: Small: Combinatorial Complexity Problems

合作研究：AF：小：组合复杂性问题

基本信息

批准号：
2007891
负责人：
Igor Pak
金额：
$ 33.91万
依托单位：
University of California-Los Angeles
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007891&HistoricalAwards=false
关键词：
Collaborative Research AF Small Combinatorial

项目摘要

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.

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