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-world activities, such as designing aircraft, analyzing DNA evidence, or breaking a secret code. This project applies recent cutting-edge work from combinatorics and algebra to more clearly determine which problems are intractable (before too many computational resources are wasted trying to solve them). This is important because, knowing that a problem is hard to solve computationally can be used in a different direction, such as creating codes that are harder to break. Combinatorics is the ancient art of counting complicated mathematical objects, and was the cradle for the development of early digital computers. Algebra here refers to the study of certain symmetries which have recently been discovered to be important in complexity theory.
More technically, this project approaches Geometric Complexity Theory from the point of view of algebraic combinatorics to further clarify feasible approaches to the VP vs. VNP Problem. Specifically, part of the work will be devoted to the computational complexity of counting certain Young tableaux and computing related constants and polynomials in Algebraic Combinatorics and Algebraic Complexity, respectively. These objects and quantities, while introduced in the beginning of last century, are still not deeply understood. However, they have recently enjoyed a healthy stream of advances from various directions. Understanding their computational nature would clarify the feasibility of some famous problems in Algebraic Combinatorics searching for natural correspondences (bijections), and pave a new approach to their study, leading towards better lower bounds in algebraic complexity. These objects and quantities include understanding the Kronecker coefficients (an 80-year-old problem), and efficiently computing Kostka and Littlewood-Richardson coefficients. While no closed-form formulas for these coefficients exist, their asymptotics can lead to new lower bounds in Geometric Complexity Theory that are currently out of reach. Specifically, distinguishing Arithmetic Complexity classes like VP and VNP boils down to distinguishing their universal polynomials (e.g. determinant vs permanent) under affine transformations, ultimately translating to inequalities between representation theoretic 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.
