Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
Christian Ikenmeyer, Igor Pak, Greta Panova · Society for Industrial and Applied Mathematics eBooks · 2023
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 absolute value and also the square of the character are 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.