Algebraic Combinatorics in Geometric Complexity Theory

Some of the oldest classical problems in algebraic combinatorics concern finding a “combinatorial interpretation”, or, more formally, a #P formula, of structure constants and multiplicities arising naturally in representation theory and algebraic geometry. Among them is the 80-year old problem of Murnaghan to find a positive combinatorial formula for the Kronecker coefficients of the symmetric group, the multiplicities of irreducible representations in tensor products. Recently these coefficients found new importance in the Geometric Complexity Theory program aimed at resolving complexity lower bounds problems like P vs NP via Algebraic Geometry and Representation Theory. Despite the little we know about Kronecker and plethysm coefficients we were able to derive positivity statements which showed that the VP vs VNP (algebraic analog of P vs NP) is even harder than originally expected, and in the meantime deepen the understanding of these coefficients and find relationships between them via complexity results.

In this talk we will introduce all the basic notions from the representation theory of the symmetric and general linear group and give some examples of how to derive positivity and briefly show how this applies to Computational Complexity which we will review as well. Based on joint works with C. Ikenmeyer, P. Burgisser.