The Computational Complexity of Plethysm Coefficients

5^th February 2020, 14:00
Nick Fischer
-

Abstract

Geometric Complexity Theory (GCT) is an ambitious approach introduced by Mulmuley and Sohoni with the far-away goal to separate algebraic complexity classes (that is, resolving the algebraic analogue of P versus NP). In that setup, a crucial role is played by certain representation-theoretic constants called plethysm coefficients. It is of particular interest to understand the computational hardness of plethysm coefficients, however, there are almost no results of that sort even for the easier problem of deciding positivity of plethysm coefficients.

In this work we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time.

This talk does not require any previous knowledge about representation theory.