The Kronecker Coefficients Of The Symmetric Group In Complexity And Combinatorics
summary
Gives concrete complexity and combinatorics: shows characters and Kronecker positivity is NP-hard, Kronecker values sit in GapP (unknown in #P), and uses Murnaghan–Nakayama, Littlewood–Richardson/hive descriptions, Barvinok’s contingency-table asymptotics and a semigroup positivity trick to get explicit positivity regimes. Key consequence: for the padded permanent vs determinant approach there are no occurrence obstructions when N ≥ M^25, so that line of GCT can’t yield superpolynomial lower bounds; also obtains tight asymptotics for rectangle cases and shape constraints for large Kronecker values.
AI-written summary · about