Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
arXiv:2207.05423 · doi:10.1093/imrn/rnad273
Abstract
We prove that deciding the vanishing of the character of the symmetric group is -complete. We use this hardness result to prove that the the square of the character is not contained in , 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 -complete under many-one reductions, and hence -hard under Turing-reductions.
arXiv comment17 pages, 2 figures, v2: expanded the exposition, added examples
References in corpus (9)
- On vanishing of Kronecker coefficients
- Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
- Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
- Strict unimodality of q-binomial coefficients
- On the complexity of computing Kronecker coefficients
- Schubert puzzles and integrability I: invariant trilinear forms
- RSK in last passage percolation: a unified approach
- The conjugacy action of and modules induced from centralisers
- Sparse multivariate polynomial interpolation in the basis of Schubert polynomials