Geometric complexity theory is an approach to P versus NP and related problems in complexity theory using algebraic geometry and representation theory. A fundamental problem in representation theory, believed to be important for this approach, is the Kronecker problem, which asks for a positive combinatorial formula for decomposing the tensor product of two irreducible representations of the symmetric group into irreducibles. The theory of quantum groups and crystal bases, which has been actively developed over the last several decades, is a powerful tool for connecting combinatorics and representation theory. In the last decade, there have been several attempts, by Berenstein, Zwicknagl, Mulmuley, Sohoni, and others, to use this tool to study the Kronecker and related plethysm problems. Recently, the investigator and his collaborators Mulmuley and Sohoni have obtained the beginnings of a theory of crystal bases for the Kronecker problem. The main goal of this project is to push this approach further. More broadly, this project aims to further explore the potentially deep connections between complexity theory and positivity in algebraic combinatorics as has been initiated by geometric complexity theory.
Objects arising in algebra are typically complicated, mysterious, and have many symmetries. Algebraic combinatorics is the study of counting and organizing such objects. This project will explore some surprising connections between this area and complexity theory (the study of algorithms and their limitations). The tensor decomposition problem is an important and difficult problem that shows up in many fields, including algebraic combinatorics, complexity theory, and statistics, and has applications in medicine, computer vision, chemistry, and fast matrix multiplication. Essentially, it is the problem of recovering individual signals from a mixture of signals. This project offers potential new insights into this problem by applying powerful tools from algebraic combinatorics.
