Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

Abstract

We prove that deciding the vanishing of the character of the symmetric group is $C_{=}P$-complete. We use this hardness result to prove that the the square of the character is not contained in $\#P$, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is $PP$-complete under many-one reductions, and hence $PH$-hard under Turing-reductions.

17 pages, 2 figures, v2: expanded the exposition, added examples

References in corpus (3)

• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• On the complexity of computing Kronecker coefficients
• RSK in last passage percolation: a unified approach

Cited by in corpus (1)

• Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy