Abstract
Geometric Complexity Theory of Mulmuley and Sohoni aimed to establish lower bounds via the separation of orbit closures of different polynomials: in the case of VP vs VNP this is equivalent to separating the orbit (under general linear group actions) of the permanent from a polynomially sized determinant. The VP vs VNP separation could also be achieved [Nisan] by replacing the determinant polynomial by a matrix power.
The separation of these orbits can be done at the level of their GL-representations and finding occurrence or multiplicity obstructions -- specific irreducible components appearing with distinct multiplicities in the two orbits under consideration. In [Burgisser-Ikenmeyer-Panova, FOCS'16, JAMS'18] we established that occurrence obstructions (i.e. zero multiplicities for one orbit, but positive for another) for the permanent versus determinant do not occur for determinants of superpolynomial size and hence VP cannot be separated from VNP this way.
In this talk we will discuss how such multiplicities can be studied via classical quantities from combinatorial representation theory (Kronecker and plethysm coefficients) and apply them to establish explicit lower bounds for the non-occurrence of obstructions in the orbits for the permanent versus determinant model ([Ikenmeyer-Panova, FOCS'16, Adv. Math'17]) and also for the orbits of permanent versus matrix power ([Gesmundo-Ikenmeyer-Panova, Diff. Geom. & Its Appl'17]). We will also show how complexity theory can lead to new representation theoretic results and how to approach some other lower bounds problems (like matrix multiplication) with these techniques.