Computer Science/Discrete Mathematics Seminar II

Geometric Complexity Theory (GCT) was developed by Mulmuley and Sohoni as an approach towards the algebraic version of the P vs NP problem, VP vs VNP, and, more generally, proving lower bounds on arithmetic circuits. Exploiting symmetries, it reduces the problem to comparing representations of the $GL_N$ orbit closures of the permanent and the determinant. Some of the multiplicities involved in this comparison are the classical “structure constants” from Algebraic Combinatorics – the Kronecker coefficients of the Symmetric Group and the plethysm coefficients for the General Linear group. It is a 80 year old problem to find a “combinatorial interpretation” (#P formula) for them.Despite the little information and limited tools available, we were able to show that all relevant multiplicities are positive. This shows that there are no “occurrence obstructions” proving superpolynomial lower bound for the permanent, thereby disproving one of the main GCT conjectures, and making the permanent vs determinant problem even harder to solve than originally expected.In this talk we will introduce GCT and the main objects and tools from Algebraic Combinatorics/Representation Theory, and then show how we prove positivity and further bounds on the relevant multiplicities.[This talk will feature results from joint works with Peter Bürgisser, Fulvio Gesmundo, Christian Ikenmeyer, Igor Pak.]