Collaborative Research: AF: Small: Combinatorial Complexity Problems

点击翻译按钮获取中文摘要

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.