The Library
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
Tools
Tools
Tools
Ikenmeyer, Christian, Pak, Igor and Panova, Greta (2023) Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. In: ACM-SIAM Symposium on Discrete Algorithms (SODA23), Florence, Italy ; Hybrid, 22-25 Jan 2023. Published in: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 3573-3586. ISBN 9781611977554. doi:10.1137/1.9781611977554.ch136
|
PDF
WRAP-positivity-symmetric-group-characters-hard-polynomial-time-hierarchy-Ikenmeyer-2022.pdf - Accepted Version - Requires a PDF viewer. Download (487Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611977554.ch136
Abstract
We prove that deciding the vanishing of the character of the symmetric group is C=Pcomplete. 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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
| Journal or Publication Title: | Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||
| ISBN: | 9781611977554 | ||||||
| Official Date: | 16 January 2023 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 3573-3586 | ||||||
| DOI: | 10.1137/1.9781611977554.ch136 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Free Access (unspecified licence, 'bronze OA') | ||||||
| Copyright Holders: | © 2023 Copyright for this paper is retained by the authors | ||||||
| Date of first compliant deposit: | 8 November 2022 | ||||||
| Date of first compliant Open Access: | 2 March 2023 | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA23) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Florence, Italy ; Hybrid | ||||||
| Date(s) of Event: | 22-25 Jan 2023 | ||||||
| Related URLs: | |||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
