Theory Lunch This Week (Thursday 10/13, 12:00, GCS 502C)

[Grayson York]

Hi all,

Please join us for theory lunch this Thursday at 12:00 in GCS 502C. Our speaker this week will be Greta Panova from the math department. She will be giving the following talk. Hope to see you all there!

Thanks,

Grayson

Title: Computational complexity in algebraic combinatorics

Abstract: Algebraic combinatorics studies discrete objects and quantities (dimensions, multiplicities etc) arising in algebra, representation theory and algebraic geometry. Most of its outstanding problems sound like "find a combinatorial interpretation for X", where X is a dimension or multiplicity and "combinatorial interpretation" means informally that X is a counting function for some nice discrete objects. As these type of problems lack formalization, we will employ the tools of computational complexity theory in order to understand the feasibility of the problems and show that squares of symmetric group characters are not in #P and so have no combinatorial interpretation.  

In the opposite direction, some of the dimensions and multiplicities (Kronecker, plethysm coefficients) subject of the open problems play a crucial role in Geometric Complexity Theory which aims to prove computational lower bounds and separate algebraic complexity classes (like VP vs VNP) using the algebraic structure and symmetries of the universal polynomials. We will briefly explain the connection and show a barrier result against some of these methods.