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 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.
more »
« less
Operations Management in the Age of the Sharing Economy: What Is Old and What Is New?
- Award ID(s):
- 1831140
- PAR ID:
- 10187211
- Date Published:
- Journal Name:
- Manufacturing and service operations management
- Volume:
- 22
- Issue:
- 1
- ISSN:
- 2616-3349
- Page Range / eLocation ID:
- 1
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
An official website of the United States government

