Collaborative Research: AF: Small: Combinatorial Complexity Problems

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

• 批准号: 2007652
• 负责人: Greta Panova
• 金额: $ 16.09万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007652&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 与 VNP 问题的可行方法。具体来说，部分工作将致力于计算某些杨氏表格的计算复杂性以及计算相关常数和多项式分别在代数组合学和代数复杂性。这些物体和数量虽然是在上世纪初引入的，但仍然没有被深入理解。然而，他们最近从各个方向取得了健康的进步。理解它们的计算性质将阐明代数组合学中寻找自然对应（双射）的一些著名问题的可行性，并为其研究铺平新的方法，从而实现更好的代数复杂性下界。这些对象和数量包括理解克罗内克系数（一个 80 年前的问题），以及有效计算 Kostka 和 Littlewood-Richardson 系数。虽然这些系数不存在封闭式公式，但它们的渐进性可能会导致几何复杂性理论中目前无法达到的新下界。具体来说，区分算术复杂性类别（如 VP 和 VNP）可以归结为区分它们的通用多项式（例如行列式与永久多项式）在仿射变换下，最终转化为涉及所提到的数量的表示理论多重性之间的不等式。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

HOOK FORMULAS FOR SKEW SHAPES IV. INCREASING TABLEAUX AND FACTORIAL GROTHENDIECK POLYNOMIALS

斜线形状的钩子公式 IV．

• 发表时间: 2022-01
• 期刊: Journal of mathematical sciences
• 作者: Alejandro Morales; Igor Pak
• 通讯作者: Igor Pak

Durfee squares, symmetric partitions and bounds on Kronecker coefficients

Durfee 平方、克罗内克系数的对称分区和界限

• DOI: 10.1016/j.jalgebra.2023.04.006
• 发表时间: 2023-09
• 期刊: Journal of Algebra
• 影响因子: 0.9
• 作者: Pak, Igor;Panova, Greta
• 通讯作者: Panova, Greta

Chromatic symmetric functions of Dyck paths and q -rook theory

Dyck路径的色对称函数和q-rook理论

• DOI: 10.1016/j.ejc.2022.103595
• 发表时间: 2023-01
• 期刊: European Journal of Combinatorics
• 影响因子: 1
• 作者: Colmenarejo, Laura;Morales, Alejandro H.;Panova, Greta
• 通讯作者: Panova, Greta

Effective Poset Inequalities

有效偏集不等式

• DOI: 10.1137/22m1532317
• 发表时间: 2023-09
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Chan, Swee Hong;Pak, Igor;Panova, Greta
• 通讯作者: Panova, Greta

Extensions of the Kahn-Saks inequality for posets of width two

宽度为 2 的偏序集的 Kahn-Saks 不等式的扩展

• DOI: 10.5070/c63160421
• 发表时间: 2023-03
• 期刊: Combinatorial Theory
• 作者: Chan, Swee Hong;Pak, Igor;Panova, Greta
• 通讯作者: Panova, Greta