When Are Monomial Symmetric Polynomials Hard?
Abstract
For a partition λ = (λ1,…,λr) and n≥ r, the monomial symmetric polynomial is defined as mλ(x1,…,xn) := ∑ xi1λ1 xi2λ2 ⋯ xirλr, where the sum ranges over all distinct monomials obtained by assigning the parts of λ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials mλ: If a family of partitions contains polynomially many distinct parts, then the corresponding monomial symmetric polynomials (on sufficiently many variables) are VNP-complete. If the number of distinct parts is constant, the family admits polynomial-size circuits. Thus the only remaining gap concerns the intermediate regime where the number of distinct parts grows subpolynomially. As part of our proof, we use combinatorial properties of matching polynomials to establish VNP-hardness of the perfect matching polynomial for blow-up graphs; these are graphs with non-generic edge-weights that are obtained by "blowing up" a smaller graph. We reduce these matching polynomials to monomial-symmetric polynomials by combining classical techniques from algebraic complexity theory with structural properties of Sidon sets.
Related
- Collision Positivity for Three-Variable Symmetric Monomial Inequalities
- Cyclotomy of symmetric polynomials
- Degree-one Pieri rule for non-symmetric Jack polynomials
- Power sums of critical points of gap polynomials for symmetric and pseudo-symmetric numerical semigroups
- Time-and-band limiting for symmetric classical Dunkl orthogonal polynomials
BibTeX
@misc{blaser2026when,
title = {{When Are Monomial Symmetric Polynomials Hard?}},
author = {Markus Bläser and Radu Curticapean and Sagnik Dutta and Gorav Jindal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25181},
eprint = {2610.25181},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25181},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When Are Monomial Symmetric Polynomials Hard?
AU - Markus Bläser
AU - Radu Curticapean
AU - Sagnik Dutta
AU - Gorav Jindal
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25181
UR - https://arxiv.org/abs/2610.25181
AB - For a partition λ = (λ_1,…,λ_r) and n≥ r, the monomial symmetric polynomial is defined as m_λ(x_1,…,x_n) := ∑ x_i_1^λ_1 x_i_2^λ_2 ⋯ x_i_r^λ_r, where the sum ranges over all distinct monomials obtained by assigning the parts of λ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials m_λ: If a family of partitions contains polynomially many distinct parts, then the corresponding monomial symmetric polynomials (on sufficiently many variables) are VNP-complete. If the number of distinct parts is constant, the family admits polynomial-size circuits. Thus the only remaining gap concerns the intermediate regime where the number of distinct parts grows subpolynomially. As part of our proof, we use combinatorial properties of matching polynomials to establish VNP-hardness of the perfect matching polynomial for blow-up graphs; these are graphs with non-generic edge-weights that are obtained by "blowing up" a smaller graph. We reduce these matching polynomials to monomial-symmetric polynomials by combining classical techniques from algebraic complexity theory with structural properties of Sidon sets.
ER -