Greta Panova (Theory Seminar)

"Geometric Complexity Theory from an Algebro-Combinatorial perspective" 
Greta Panova (USC)
Monday, January 27, 2020, 2:00pm
EBU3B, Room 4258

Abstract: Geometric Complexity Theory was developed by Mulmuley and Sohoni in the past more than 20+ years to separate algebraic complexity classes (VP vs VNP) by studying their representative polynomials (e.g. determinant and permanent) via their underlying symmetries and tools from Representation Theory and Algebraic Geometry. We will explain the basic setup of VP vs VNP and GCT, and show that the GCT approach turned out to be much harder than expected: there are no "occurrence obstructions"   which would show a superpolynomial bound for permanent vs determinant. We will discuss other models where such approaches could be applied, and show a toy model where GCT works despite the lack of occurrence obstruction.
We will not assume any knowledge of Representation Theory nor Algebraic Geometry. Based on joint works with B\"urgisser, D\"orfler, and Ikenmeyer.