  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.
