Greta Panova

Speaker: Greta Panova, University of Pennsylvania

Title: Kronecker and plethysm coefficients in Geometric Complexity Theory

Abstract: Some of the outstanding and still classical problems in Algebraic Combinatorics concern understanding the Kronecker coefficients of the symmetric group, the multiplicities describing the decomposition of tensor products of representations into irreducibles, which are nonnegative integers lacking a positive combinatorial formula for over 75 years. Recently they appeared in Geometric Complexity Theory (GCT), a program aimed to distinguish computational complexity classes (like the P vs NP problem) and prove complexity theoretic bounds using Algebraic Geometry and Representation Theory.

In this talk we will describe the setup and how the Kronecker and plethysm coefficients arise and show how despite any useful formulas, positivity can still be shown in the GCT setting disproving the existence of the so-called "occurrence obstructions". Using algebraic and combinatorial methods, we [Burgisser-Ikenmeyer-P, Ikenmeyer-P] show that the relevant Kronecker and plethysm coefficients of the general linear group are positive, thereby disproving a Mulmuley and Sohoni conjecture on the existence of "occurrence obstructions" and practically showing that the 'P vs NP' problem is even more difficult. In the reverse direction, GCT arguments show that rectangular Kronecker coefficients are larger than plethysm coefficient in a stable range [Ikenmyer-P], establishing a connection between apriori unrelated and greatly mysterious multiplicities. The GCT paradigm is applicable also to other complexity lower bounds, or other models like comparing permanent versus iterated matrix multiplication, and the relevant multiplicities can also be expressed in terms of plethysms and (symmetric) Kronecker coefficients. We [Gesmundo-Ikenmeyer-P] show that in a simplified permanent versus matrix powering model the multiplicity of an irreducible representation [$\lambda$] in the orbit of the trace of a matrix power is a sum of symmetric Koneckers, which is positive in all cases of interest and hence there are again no occurrence obstructions here.