Collaborative Research: AF: Small: Computational Complexity and Algebraic Combinatorics

University Of Southern California, Los Angeles CA

Investigators

Abstract

This project aims to study a variety of problems centered around certain numbers and polynomials that describe fundamental symmetries in algebra and geometry. Despite their fundamental nature and century-long history, these objects have been largely mysterious and remain at the heart of recent developments in algebraic combinatorics. The main goal is to understand their computational nature and behavior, which would have far-reaching implications across many fields. In one direction, the researchers aim to explain, using the framework of Computational Complexity theory, why these objects are so difficult to understand. In another direction, they aim to use these objects and quantities to establish the computational complexity of certain fundamental polynomials. Specifically, the project lies in the intersection of Computational Complexity and Algebraic Combinatorics. The goal is to advance the understanding of the asymptotics and the complexity of computing several structure constants such as Kronecker, plethysm, and Schubert coefficients that comprise some of the main open problems in algebraic combinatorics. Their computational complexity would explain why these structure constants have remained so elusive despite decades of research and would hint at what solutions to expect. Understanding their behavior and asymptotics can lead to new lower bounds on fundamental problems and polynomials in Geometric Complexity Theory, such as the complexity of matrix multiplication and computing the permanent. Viewed broadly, the project works towards the separation of the computational complexity classes VP and VNP, which represent the algebraic analogues of the well-known complexity classes P and NP, respectively. 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.