Seminar

http://events.berkeley.edu/index.php/calendar/sn/math.html?event_ID=115895

A major 80-year old problem in Algebraic Combinatorics concerns the Kronecker coefficients of the symmetric group – the multiplicities of irreducible representations in the decomposition of the tensor product of irreducible representations, or more formally – showing that computing these coefficients is in #P. The flagship problem in Algebraic Complexity Theory is the "VP vs VNP" problem, which is the algebraic analogue of the famous "P vs NP". The Geometric Complexity Theory (GCT) program aims to prove that VP is not equal to VNP, and in general prove complexity lower bounds, by distinguishing polynomials via their symmetries (more precisely, the GL-representations of the coordinate rings of their corresponding GL orbit closures).

We will start with the basics on Kronecker coefficients, and, despite the limited information, use them to solve problems in combinatorics (e.g. unimodality and lower bounds). We will then define boolean and arithmetic circuit complexity and explain GCT, where we will show how the Kronecker coefficients can be used to show that the VP vs VNP problem is harder to solve than expected.

In particular, VP not equal to VNP is equivalent to "the permanent of an [X_ij] variable not equal to a polynomially size determinant with affine linear entries in the variables". A main approach in GCT was to distinguish the permanent from the determinant via an "occurrence obstruction" – an irreducible GL-representation which appears in the coordinate ring of the orbit closure of the permanent of size m, but not in the corresponding ring for a superpolynomially(in m)-sized determinant. We show that such occurrence obstructions do not exist if the determinant is of size >m^25, and hence this approach fails.