On Vanishing of Kronecker Coefficients

We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. We do so by providing a positive #P-formula for a subclass of Kronecker coefficients whose positivity is NP-hard to decide. We use this insight to construct many partition triples with few rows inside the Kronecker cone that have a vanishing Kronecker coefficient. This result takes a step towards proving the existence of occurrence-based representation-theoretic obstructions in the context of the geometric complexity theory approach to the permanent vs. determinant problem. Its proof also illustrates the effectiveness of the explicit proof strategy of geometric complexity theory.