Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives on their own and brought us some beautiful formulas and combinatorial interpretations.
The flagship hook-length formula counts the number of standard Young tableaux, which also give the dimension of the irreducible Specht modules of the symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.
We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, which can formally explain the beauty we see and the difficulties we encounter in finding further formulas and “combinatorial interpretations”. In the opposite direction, the 85 year old open problem on Kronecker coefficients of the symmetric group lead to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation-theoretic multiplicities in further detail, possibly asymptotically.
This is the first part of two talks, the second of which may be found here.
This video is part of Harvard University‘s conference Current Developments in Mathematics 2023.
