Mathematical Sciences Research Institute

Home » UC Berkeley Colloquium: From Algebraic Combinatorics to Geometric Complexity Theory


UC Berkeley Colloquium: From Algebraic Combinatorics to Geometric Complexity Theory March 08, 2018 (04:10 PM PST - 05:00 PM PST)
Parent Program: --
Location: 60 Evans Hall
Speaker(s) Greta Panova (University of Southern California)
Description No Description
No Video Uploaded


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.

No Notes/Supplements Uploaded No Video Files Uploaded