pipette
ESEspañol

When Are Monomial Symmetric Polynomials Hard?

Markus Bl\"aser, Radu Curticapean, Sagnik Dutta, Gorav Jindal

Preprint

In the authors' words

For a partition and , the monomial symmetric polynomial is defined as 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 : 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.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 20 pages, 3 figures. Accepted at SODA 2027