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 与 VNP 问题的可行方法。具体来说，部分工作将致力于计算某些杨氏表格的计算复杂性以及计算相关常数和多项式分别在代数组合学和代数复杂性。这些物体和数量虽然是在上世纪初引入的，但仍然没有被深入理解。然而，他们最近从各个方向取得了健康的进步。理解它们的计算性质将阐明代数组合学中寻找自然对应（双射）的一些著名问题的可行性，并为其研究铺平新的方法，从而实现更好的代数复杂性下界。这些对象和数量包括理解克罗内克系数（一个 80 年前的问题），以及有效计算 Kostka 和 Littlewood-Richardson 系数。虽然这些系数不存在封闭式公式，但它们的渐进性可能会导致几何复杂性理论中目前无法达到的新下界。具体来说，区分算术复杂性类别（如 VP 和 VNP）可以归结为区分它们的通用多项式（例如行列式与永久多项式）在仿射变换下，最终转化为涉及所提到的数量的表示理论多重性之间的不等式。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

What is a combinatorial interpretation?

什么是组合解释？

• 发表时间: 2023-01
• 期刊: Open Problem in Algebraic Combinatorics
• 作者: Pak; Igor
• 通讯作者: Igor

Log-Concavity in Planar Random Walks

平面随机游走中的对数凹性

• DOI: 10.1007/s00493-021-4860-7
• 发表时间: 2022-09
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Chan, Swee Hong;Pak, Igor;Panova, Greta
• 通讯作者: Panova, Greta

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

对称群特征的正性与多项式时间层次一样困难

• 发表时间: 2023-01
• 期刊: Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Ikenmeyer, Christian;Pak, Igor;Panova, Greta
• 通讯作者: Panova, Greta

What is in #P and what is not?

里面有什么

• 发表时间: 2022-10
• 期刊: Annual Symposium on Foundations of Computer Science
• 作者: Ikenmeyer, Christian;Pak, Igor
• 通讯作者: Pak, Igor

Skew shape asymptotics, a case-based introduction

斜形渐近，基于案例的介绍

• 发表时间: 2021-05
• 期刊: Seminaire lotharingien de combinatoire
• 作者: Pak; Igor
• 通讯作者: Igor