Monomial symmetric polynomial complexity hinges on distinct partition parts
When Are Monomial Symmetric Polynomials Hard?
Computational ComplexitySymbolic Computation
Summary
This paper studies when calculating specific polynomial expressions, called monomial symmetric polynomials, becomes computationally difficult. The authors find that if the number of different parts in the polynomial's defining sequence grows quickly with size, then computing these polynomials is as hard as the hardest problems in a certain complexity class (VNP-complete). But if the number of distinct parts stays small, the computations can be done efficiently. The paper also explores related graph problems and uses new mathematical techniques to establish these results.
What this means in practice
- •For complexity theorists: Determine which classes of symmetric polynomials are computationally feasible, shaping the design of efficient algebraic algorithms.
- •For graph algorithm designers: Use hardness results on matching polynomials of blow-up graphs to guide the development of exact or approximate graph computations.
A theory result. No direct application yet.
Authors
Markus Bläser, Radu Curticapean, Sagnik Dutta, Gorav Jindal
Abstract
For a partition $\boldsymbolλ = (λ_1,\ldots,λ_r)$ and $n\ge r$, the monomial symmetric polynomial is defined as $$m_{\boldsymbolλ}(x_1,\ldots,x_n) := \sum x_{i_1}^{λ_1} x_{i_2}^{λ_2} \cdots x_{i_r}^{λ_r},$$ where the sum ranges over all distinct monomials obtained by assigning the parts of $\boldsymbolλ$ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials $m_{\boldsymbolλ}$: 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.