When Are Monomial Symmetric Polynomials Hard?

Introduction

Symmetry is a fundamental concept in mathematics and computer science, appearing across algebra, combinatorics, and theoretical computer science. In algebra, it appears prominently with the class of symmetric polynomials, i.e., polynomials which are invariant under any permutation of their variables. Symmetric polynomials have been extensively studied in algebraic combinatorics and invariant theory, and they naturally arise in counting problems and algebraic computation. Understanding the computational complexity of natural families of symmetric polynomials is therefore a central question in algebraic complexity theory.

In algebraic complexity theory, the underlying complexity measure is usually the size of arithmetic circuits computing the polynomial. An arithmetic circuit is a directed acyclic graph whose internal nodes are labeled by addition or multiplication gates, and whose leaves are labeled by input variables or field constants. The arithmetic complexity $L(f)$ of a polynomial $f \in\mathbb{F}[x_1,\ldots,x_n]$ is the minimum size of an arithmetic circuit computing it, where circuit size is the number of nodes. We refer the reader to the surveys [18 SY10, Sap15, 6] for background on algebraic complexity theory.

Monomial symmetric polynomials. In this paper, we investigate the circuit complexity of monomial symmetric polynomials. Let $\boldsymbol{\lambda}=(\lambda_1,\ldots,\lambda_r)$ be a partition with $\lambda_1\geq\cdots\geq\lambda_r>0$. The monomial symmetric polynomial $m_{\boldsymbol{\lambda}}$ associated with $\boldsymbol{\lambda}$ in $n$ variables is

where the sum ranges over all distinct monomials obtained by assigning the parts of $\boldsymbol{\lambda}$ to pairwise distinct variables; equivalently, we sum over the $S_n$-orbit but keep each resulting monomial only once.

The family of monomial symmetric polynomials forms one of the standard bases of the ring of symmetric polynomials and plays a fundamental role in algebraic combinatorics and representation theory. Classical symmetric polynomials, such as elementary and power symmetric polynomials, can be viewed as special cases of monomial symmetric polynomials for specific partitions. For instance, the $k$-th elementary symmetric polynomial is $e_k=m_{(1,1,\ldots,1)}$, while the $k$-th power sum symmetric polynomial is $p_k=m_{(k)}$.

Complexity of Symmetric Polynomials.

Symmetric polynomials have been studied in algebraic complexity theory for decades. As a first question, one can ask whether there exist any families of symmetric polynomials that require super-polynomial-size arithmetic circuits. Since we lack superpolynomial circuit lower bounds for explicit families, these results either need to address restricted models or require complexity-theoretic assumptions.

Unconditional lower bounds. A seminal result of Nisan and Wigderson [NW96] established that elementary symmetric polynomials $e_k(x_1,\ldots,x_n)$ require exponential-size homogeneous depth-three circuits over fields of characteristic zero when $k$ is even, $k=\Theta(n)$, and $k\leq n/3$. For non-homogeneous depth-three formulas, Shpilka and Wigderson [SW99] prove a quadratic lower bound for computing $e_k(x_1,\ldots,x_n)$ when $k=\Theta(n)$ and $k\leq2n/3$, which is tight. The upper bound is due to Ben-Or, see [SW99, Thm. 4.2]. Hrubeš and Yehudayoff [12] investigate formulas of arbitrary depth. They prove that, for $n\geq2k$, every multilinear homogeneous formula for $e_k(x_1,\ldots,x_n)$ has size $k^{\Omega(\log k)}n$ and construct homogeneous formulas of matching size, which are, however, not multilinear. Fournier et al. [FLMS17] study the shifted partial derivative complexity of elementary symmetric polynomials, strengthening the results of Nisan and Wigderson in certain parameter regimes. Despite this rich history, the complexity of monomial symmetric polynomials has remained largely open.

Conditional lower bounds. Bläser and Jindal [3] constructed families of symmetric polynomials that require circuits of superpolynomial size assuming $\mathrm{VP}\ne\mathrm{VNP}$. More precisely, their families are VNP-complete under $c$-reductions, which implies they cannot be computed by polynomial-size arithmetic circuits unless $\mathrm{VP}=\mathrm{VNP}$. Here, $c$-reductions are the algebraic analogue of Turing reductions in classical complexity theory, allowing for oracle access to the polynomial being reduced to, see Appendix § 6 and § 2 for a formal definition.

The main tool of Bläser and Jindal is an effective version of the fundamental theorem for symmetric polynomials (Theorem A.1) in terms of circuit complexity: If $(f_n)$ is a family of VNP-complete polynomials, then the polynomial family $g_n$ defined by $g_n := f_n(e_1,e_2,\ldots,e_{v(n)})$ is a family of symmetric polynomials that is VNP-complete under $c$-reductions, where $e_i$ is the $i$-th elementary symmetric polynomial and $v(n)$ is the number of variables in $f_n$. Chaugule et al. [CKL+23] prove a similar result for formulas, and Bhattacharjee et al. [4] prove a constant-depth analogue.

Similar techniques also apply to Schur polynomials, another basis family of symmetric polynomials that play a central role in algebraic combinatorics and representation theory. They can be defined as specific determinants, and Chaugule et al. [CKL+23] show that for certain families of partitions, Schur polynomials are hard for VBP. Thus, if these specific determinants had algebraic formulas of polynomial size, then so would the ordinary determinants.

Known results for monomial-symmetric polynomials. Curticapean et al. [CLS22] constructed an explicit family of monomial-symmetric polynomials that are VNP-complete under $c$-reductions. Their hard family is specifically constructed to enable the hardness result. For example, the chosen partition has only distinct parts, and more importantly, these parts essentially enjoy the highly non-generic property of forming a Sidon set, i.e., a set of integers $S$ such that $x,y \in S$ can be recovered uniquely from $x+y$.

The result in [CLS22] was shown through a $c$-reduction from the VNP-complete perfect matching polynomials to monomial symmetric polynomials. The starting point is the Binet–Minc identity (Theorem 2.1), which expresses monomial symmetric polynomials in terms of power sum symmetric polynomials as

for some “witnessing polynomial” $f$, where $d$ is the degree of $m_\lambda$ and $p_i$ is the $i$-th power sum symmetric polynomial. By crucially using the Sidon properties of $\lambda$ and additional technical conditions on $\lambda$, a relatively direct reduction from perfect matching polynomials to this witnessing polynomial $f$ can be established. Then, using results from [CKL+23, BJ19], the witnessing polynomial $f(y_1,y_2,\ldots,y_d)$ is $c$-reduced to the monomial-symmetric polynomial $m_\lambda$, giving the overall VNP-hardness result.

Our Results.

We establish an almost-complete dichotomy for the algebraic complexity of monomial symmetric polynomials in terms of the number of distinct parts in the defining partition: At one end, a constant number of distinct parts leads to polynomial-size circuits. At the other end, polynomially many distinct parts lead to VNP-completeness under $c$-reductions, provided that the number of variables in $m_\lambda$ is large enough.

The tractable side of our classification is folklore; we state a bound for completeness in Appendix § 7.

Our classification has two limitations: First, Theorem 1.1 requires that the number of variables is at least the degree of the polynomials in question. This is a genuine limitation. For example, the Vandermonde permanent discussed in § 5 has degree $\binom{n+1}{2}$ but only $n$ variables, making our theorem inapplicable.

Second, the classification leaves a blind spot in the intermediate regime where the number of distinct parts grows sub-polynomially in $n$. A similar situation occurred in the classification of immanants, another family of polynomials that are indexed by partitions $\lambda$. Bürgisser [5] proved the first hardness results for certain immanants, and Curticapean [Cur21] later obtained a full dichotomy. Curiously, this dichotomy does address regimes of sub-polynomially growing hardness parameters by using assumptions from parameterized complexity theory. In our setting of monomial symmetric polynomials, both this issue and the overall hardness proof appear significantly more difficult: Immanants have matrix inputs, which directly give a very useful graph-theoretic structure that allows for a reduction from matchings, whereas hardness proofs for monomial symmetric polynomials have to recover this matching structure from additive relations among these exponents. We return to this in § 5.

Proof Ideas.

As in previous works [CLS22], we construct a $c$-reduction from the VNP-complete perfect matching polynomials to monomial symmetric polynomials. We start again from the Binet–Minc identity (Theorem 2.1) that expresses $m_\lambda$ of degree $d$ in terms of the power sum symmetric polynomials $p_i$, as sketched above for [CLS22]. That is,

For arbitrary partitions $\lambda$ with many distinct parts, two new technical issues arise:

• First, for general $\lambda$, we have no chance of controlling the additive relations among all distinct parts of $\lambda$, so we must ensure carefully that we can extract a well-behaved subset. Indeed, we manage to extract a large sum-free Sidon subset from the distinct parts of $\lambda$.

• Second, repeated parts are a nontrivial issue that was invisible in the previous approaches. Repetitions essentially turn a generic graph into a blow-up graph, where each selected part contributes a vertex block of size equal to the number of repetitions. Proving that the corresponding blow-up matching polynomials remain hard is a central new ingredient of the paper, and it is also a source of structured, non-generic permanent-like polynomial families.

In more detail, our proof strategy is as follows. Suppose that

where $\mu_1>\mu_2>\cdots>\mu_t$ are the distinct parts of $\lambda$, and $w_i$ is the multiplicity of $\mu_i$ in $\lambda$. The Binet–Minc identity establishes a correspondence between monomials of $f$ and set partitions of $[k]$. From the set $\{\mu_1,\ldots,\mu_t\}$ we extract a sum-free Sidon subset $S$ of size $\Omega(\sqrt{t})$. The Sidon property makes pairwise sums of elements of $S$ uniquely decodable, and these sums will become edge variables of a complete graph.

We then take a carefully chosen homogeneous component of $f$ and set $y_\mu=0$ for every $\mu\in S$. This removes singleton blocks whose labels lie in $S$. Through a counting argument, we can force every surviving set partition to use all elements outside $S$ as singleton blocks, while the copies of elements in $S$ must be paired into blocks of size two; larger blocks would leave too few blocks in total. After dividing out the forced singleton contribution from the elements outside $S$, the remaining monomials are exactly encoded by pairings among the copies of elements of $S$.

If every selected part occurs once, these pairings are perfect matchings of a complete graph on $\Omega(\sqrt{t})$ vertices, recovering essentially the situation from [CLS22]. With multiplicities however, each selected part $\mu_i$ contributes $w_i$ indistinguishable copies, and the extracted polynomial is the perfect matching polynomial of a blow-up of the complete graph. The blow-up graph replaces vertex $i$ by a clique of size $w_i$; see Figure 3 for an example and § 2 for the formal definition.

In § 3, we reduce the ordinary perfect matching polynomial to the perfect matching polynomial of a blow-up of a complete graph with arbitrary positive multiplicities and an even total number of vertices. The reduction attaches private gadget blocks and chooses algebraic edge-weights so that, after taking the right homogeneous component, every original block is used exactly once.

Organization of the Paper.

In § 2, we introduce the necessary background and notation. In § 3, we reduce the perfect matching polynomial to its blown-up version for arbitrary positive multiplicities with an even total sum. Finally, in § 4, we reduce the blown-up perfect matching polynomial to the monomial symmetric polynomial $m_\lambda$. Open problems are discussed in § 5. Appendix § 6 and Appendix § 7 contain background material and omitted proofs.

Preliminaries.

We refer to Section A.2 for a basic introduction to algebraic complexity. We will be working with $c$-reductions, which are the algebraic analogue of Turing reductions from classical complexity theory. The oracle complexity of a polynomial $f$ with respect to another polynomial $g$ is the minimum size of an arithmetic circuit computing $f$ that is allowed to query an oracle for $g$, denoted by $L^{g}(f)$. For more details on $c$-reductions, see Section A.2.

Notation for Partitions.

A partition $\lambda$ of a positive integer $d$ is a tuple of positive integers $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ such that $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_k>0$ and $\sum_{i=1}^{k}\lambda_i=d$. We write $\lambda\vdash d$. For a partition $\lambda$, we define:

We also use a shorthand notation for partitions with repeated parts. If $\mu_1>\mu_2>\cdots>\mu_t$ (with $t=D(\lambda)$) are the distinct parts of $\lambda$ with multiplicities $w_1,w_2,\ldots,w_t$ respectively, we write

The Ring of Symmetric Polynomials.

Unless stated otherwise, we assume that the underlying field $\mathbb{F}$ is $\mathbb{C}$. A polynomial $f\in\mathbb{F}[x_1,x_2,\ldots,x_n]$ is called symmetric if, for every permutation $\sigma\in S_n$, we have

The ring of symmetric polynomials in $n$ variables admits two natural sets of algebraically independent generators: the elementary symmetric polynomials $e_1,\ldots,e_n$ and the power sum symmetric polynomials $p_1,\ldots,p_n$, defined for $k\in[n]$ by

Every symmetric polynomial can be uniquely expressed as a polynomial in the elementary symmetric polynomials, and also as a polynomial in the power sum symmetric polynomials. See Section A.1 for details. For a symmetric polynomial $f$, we define $f^{\mathrm{elem}}$ and $f^{\mathrm{pow}}$ to be the unique polynomials in $\mathbb{F}[y_1,\ldots,y_n]$ such that

Matching Polynomials.

Let $G$ be an $n$-vertex graph whose edges are labelled by variables from a set $\mathbf{X}$ or constants from $\mathbb{F}$. For a matching $M$ of $G$, denote its weight by $\operatorname{wt}(M)$; this is the product of the weights of the edges in $M$. The matching polynomial of $G$, denoted $\operatorname{Match}(G) \in\mathbb{F}[\mathbf{X}]$, is defined as

where $M$ ranges over all matchings of $G$. In a similar way, the perfect matching polynomial of $G$ is defined by

where the sum ranges over all perfect matchings $M$ of $G.

Assume that $n \in\mathbb{N}$ is even. Let $\mathbf{X}_n := \{x_{i,j} \mid1 \le i < j \le n\}$ be the set of $\binom{n}{2}$ variables corresponding to the edges of the complete graph $K_n$. We consider the edge $(i,j) \in E(K_n)$ to be weighted by $x_{i,j}$. The VNP-completeness of the permanent [Val79] implies VNP-completeness of the polynomial

Indeed we have $\operatorname{Per}(A) = \operatorname{PerfMatch}(G)$ for the complete bipartite graph $G$ whose edge $(i,j)$ has weight $A_{i,j}$.

We will also consider the so-called blow-up matching polynomials of complete graphs. For any $n \in\mathbb{N}$ and a vector $\mathbf{w} = (w_1,w_2,\ldots,w_n)$ of positive integers, the $\mathbf{w}$-blow-up of $K_n$, denoted $K_n^{(\mathbf{w})}$, is the edge-weighted graph obtained by replacing each vertex $i$ with a clique of size $w_i$, and replacing each edge $\{i,j\}$ with a complete bipartite graph between the corresponding cliques. See Figure 1 for an example. Every edge between blocks $i$ and $j$ has weight $x_{i,j}$. The edges inside block $i$ have weight $z_i$, where $z_i$ is a new variable. Thus the underlying unweighted graph is complete on $\sum_i w_i$ vertices, but its edge weights are shared according to the blocks.

For a vector $\mathbf{w} \in\mathbb{Z}_{>0}^n$, we define the polynomials $\operatorname{Match}_n^{(\mathbf{w})}$ and $\operatorname{PerfMatch}_n^{(\mathbf{w})}$ to be the matching polynomial and the perfect matching polynomial, respectively, of the blow-up graph $K_n^{(\mathbf{w})}$. Throughout the paper, blow-up vectors have strictly positive integer entries. (A zero entry would simply delete the corresponding vertex and could be removed in advance.)

Monomial Symmetric Polynomials and Rectangular Permanents.

Fix a $k \times n$ matrix $X$ where $k \le n$ and the $(i,j)$-th entry of $X$ is a variable $x_{i,j}$. For a positive integer $m$, we denote by $[m]$ the set $\{1,2,\ldots,m\}$. For a subset $J \subseteq[n]$ of size $k$, we denote by $X_J$ the submatrix obtained by keeping only the columns indexed by $J$. The rectangular permanent $\operatorname{rPer}_{k,n}$ is defined by

The following polynomial identity will play a key role in our arguments. For a positive integer $k$, let $\mathcal{P}_k$ denote the set of all partitions of $[k]$ into non-empty subsets.

Theorem 2.1 (Binet–Minc Identity [19]). Let $\mathbb{F}$ be any field and let $X$ be a $k \times n$ matrix as above. Then

Recall that the monomial symmetric polynomial $m_{\lambda}(x_1,x_2,\ldots,x_n)$ associated with the partition $\lambda$ in $n$ variables is defined as

Here the sum ranges over all distinct monomials obtained by assigning the parts of $\lambda$ to pairwise distinct variables; equivalently, over all monomials whose nonzero exponent multiset is $\{\lambda_1,\ldots,\lambda_k\}$. When the number of variables is clear from the context, we simply write $m_{\lambda}$.

Write $\lambda=(\mu_1^{w_1},\ldots,\mu_t^{w_t})$, where the $\mu_j$ are distinct, and put $\kappa(\lambda):=\prod_{j=1}^{t}w_j!$. For $k\le n$, we have

Indeed, the rectangular permanent sums over injective assignments of rows to columns. Each distinct monomial occurs exactly $\kappa(\lambda)$ times, since the $w_j$ rows with exponent $\mu_j$ can be assigned to their chosen columns in $w_j!$ ways. For the matrix above, the block sums in Theorem 2.1 are

Dividing the Binet–Minc identity by $\kappa(\lambda)$ therefore yields the following formula.

Corollary 2.2. Let $\lambda=(\lambda_1,\ldots,\lambda_k)=(\mu_1^{w_1},\ldots,\mu_t^{w_t})$ be a partition with distinct parts $\mu_1,\ldots,\mu_t$, and let $n\ge k$. Over a field of characteristic zero,

where $\kappa(\lambda)=\prod_{j=1}^{t}w_j!$ and $\lambda_I=\sum_{i\in I}\lambda_i$.

Tools from Additive Combinatorics.

To extract the perfect matching polynomial of complete graphs from the power-sum representation of $m_\lambda$, we also need the notion of Sidon sets. A set of positive integers $S$ is called a Sidon set if, for any four elements $a,b,c,d \in S$, the equality

implies that the unordered pairs $\{a,b\}$ and $\{c,d\}$ are equal. In other words, unordered pairwise sums are distinct. We will use the following classical result on the existence of large Sidon subsets of finite sets of positive integers.

We shall need a slightly stronger version of the above theorem, in the sense that we want Sidon subsets $S \subseteq A$ such that the sum of two elements of $S$ is not equal to any element of $S$. This stronger version (Corollary 2.5) follows from the following result of Erdős [10].

Sets $S$ as above are called sum-free. The above theorem states that every finite set of non-zero real numbers contains a large sum-free subset. The following corollary is an immediate consequence of Theorem 2.3 and Theorem 2.4.

Proof. First apply Theorem 2.4 to obtain a sum-free subset $A' \subseteq A$ of size at least $|A|/3$. If $|A|$ is sufficiently large, then so is $|A'|$, so we can apply Theorem 2.3 to $A'$ and obtain a Sidon subset $S \subseteq A'$ with

Since $S \subseteq A'$, the sum-free property is preserved. $\square$

Hardness of Blown-Up Matching Polynomials.

In this section, we reduce the multiplicity-free perfect matching polynomial to its blown-up version. This will allow us later to handle $m_\lambda$ for partitions $\lambda$ with repeating parts; the repetitions correspond to blow-ups. The main result of this section is the following lemma.

Throughout this section, fix $r \ge4$ and $t:=2\lfloor r/4\rfloor$ and $\mathbf{w}\in\mathbb{Z}_{\ge0}^r$ as above. Our reduction proceeds along the following chain, established in Lemma 3.4 and Lemma 3.5:

Graph construction. Let us write $a_i=w_i$ and $b_i=w_{t+i}$ for $i\in[t]$. Without loss of generality, we assume that $\mathbf{w}$ is non-increasing. In particular, this implies that $a_i\ge b_i$ for all $i\in[t]$. We obtain a weighted gadget $\Gamma_{\mathbf{w}}$ from $K_r^{(\mathbf{w})}$ by making the following substitutions and deleting zero-weight edges:

• Introduce a new indeterminate $z$ and set $x_{i,j}\leftarrow z\cdot x_{i,j}$ for all $1\le i<j\le t$.

• Set $x_{i,t+i}\leftarrow\xi_i$ for $1\le i\le t$, where $\xi_i$ will be determined later. The choice of $\xi_i$ is crucial.

• Set $x_{i,j}\leftarrow0$ for all $1\le i<j\le r$ not covered in the previous two steps.

• Set every intra-block variable $z_i$ of $\operatorname{Match}_{r}^{(\mathbf{w})}$ to $0.

Thus $\operatorname{Match}(\Gamma_{\mathbf{w}})$ is a specialization of $\operatorname{Match}_{r}^{(\mathbf{w})}$. Only the first $2t=4\lfloor r/4\rfloor$ blocks are relevant; every vertex in the remaining (at most three) blocks is isolated in $\Gamma_{\mathbf{w}}$. Figure 2 shows the case $r=8$ and $t=4$, with the four original blocks having the same sizes and positions as in Figure 1. Note that we cannot control the blow-up $\mathbf{w}$; the vector $\mathbf{w}$ can be viewed as adversarial.

For $i\in[t]$, let $A_i$ be the vertex block in $\Gamma_{\mathbf{w}}$ corresponding to vertex $i$ of $K_r$, and let $B_i$ be the block corresponding to vertex $t+i$. We will call $A_1\cup\ldots\cup A_t$ the “original” vertices of $\Gamma_{\mathbf{w}}$ and $B_1\cup\ldots\cup B_t$ the “gadget” vertices. Note that each block $A_i$ of original vertices has a private block $B_i$ of gadget vertices; there are no edges between $A_i$ and $B_j$ for $i\ne j$.

First step. The reduction from $\operatorname{PerfMatch}_t$ to $\operatorname{Match}_{r}^{(\mathbf{w})}$ proceeds as follows: Every matching $M$ in $\Gamma_{\mathbf{w}}$ is the union of an “original matching” $O$ that lives within the original blocks and, for each $i\in[t]$, some matching between the original block $A_i$ and its gadget block $B_i$. In other words, each matching $O$ on the original part can be extended in several ways to a matching of the overall graph $\Gamma_{\mathbf{w}}$ by adding gadget edges. For each $i\in[t]$, the edge-weight $\xi_i$ on the gadget edges between $A_i$ and $B_i$ is chosen carefully to ensure that the weighted count of extensions vanishes if $O$ leaves all vertices of $A_i$ unmatched. The required weights $\xi_i$ are supplied by the following lemma, which is proven in Appendix § 8 of the appendix.

there is $\xi=\xi(a,b)\in\mathbb{C}$ such that

The isolation weights let us recover perfect matchings from the blown-up matching polynomial. The following lemma makes this reduction precise.

Proof. Use the graph $\Gamma_{\mathbf{w}}$ and blocks $A_i,B_i$ defined above. Choose $\xi_i:=\xi(a_i,b_i)$ by Lemma 3.2, and put

We obtain the required $c$-reduction by proving that

To prove Equation (5), let $\mathcal{O}$ be the set of matchings with exactly $t/2$ edges in the graph $\Gamma_{\mathbf{w}}[A_1\cup\ldots\cup A_t]$ induced by original blocks. We call these the original matchings. For every original matching $O\in\mathcal{O}$, define its type $\theta_O$ to be the map with domain $[t]$ that maps $i\mapsto|V(O)\cap A_i|$. An original matching $O\in\mathcal{O}$ is a lift if $\theta_O(i)=1$ for all $i\in[t]$. For an original edge $e$ between blocks $A_i$ and $A_j$, let $\bar{w}(e):=x_{ij}$ be its weight after removing the auxiliary factor $z$.

Each lift corresponds to a perfect matching in $K_t$ by consolidating each block $A_i$ of $\Gamma_{\mathbf{w}}$ to a single vertex $i$ in $K_t$. Conversely, each perfect matching in $K_t$ corresponds to $\prod_{i=1}^{t}a_i$ lifts in $\Gamma_{\mathbf{w}}$ by independently choosing, for each block $i$, one of $a_i$ vertices in block $A_i$. The correspondence preserves the weights $\bar{w}(e)$ of the original edges, so the weighted count of lifts equals that of perfect matchings in $K_t$, up to the factor $\prod_{i=1}^{t}a_i$.

In view of this, we aim at restricting the matchings counted in $[z^{t/2}]\operatorname{Match}(\Gamma_{\mathbf{w}})$ to lifts. For $O\in\mathcal{O}$, let $\mathcal{E}_O$ be the set of matchings on gadget edges that extend $O$ to a matching $M$ in $\Gamma_{\mathbf{w}}$. Every matching of $z$-degree $t/2$ has a unique decomposition $O\cup F$, where $O\in\mathcal{O}$ and $F\in\mathcal{E}_O$. Hence

We show that the gadget extensions $q(O)$ restrict the summation to lifts $O$. To abbreviate, let us write $\theta:=\theta_O$ and write $Q_i^\theta$ for the complete bipartite graph with $a_i-\theta(i)$ left and $b_i$ right vertices. We observe that

For the first equation, note that the sum defining $q(O)$ in Equation (6) ranges over all matchings in the disjoint union of complete bipartite graphs $Q_1^\theta\cup\cdots\cup Q_t^\theta$, where $Q_i^\theta$ has weight $\xi_i$ on all edges. For the second equation:

• If $O$ is not a lift, we show that $q(O)=0$. Indeed, if $O$ is not a lift, then $\theta(i)=0$ for some $i\in[t]$, because $O$ is a matching with $t/2$ edges by definition, so an index $j$ with $\theta(j)>1$ forces some index $i$ with $\theta(i)=0$. Then $Q_i^\theta\cong K_{a_i,b_i}$ and our choice of $\xi_i$ by Lemma 3.2 ensures that the $i$-th factor in Equation (7) is $M(Q_i^\theta,\xi_i)=0$, which overall implies $q(O)=0$.

• If $O$ is a lift, then $Q_i^\theta\cong K_{a_i-1,b_i}$ for all $i$, so the factors in Equation (7) for $i\in[t]$ are $M(Q_i^\theta,\xi_i)=\eta_i\ne0$.

Substituting Equation (7) into Equation (6), we obtain

where the second equality follows from an earlier observation: every perfect matching in $K_t$ corresponds to $\prod_i a_i$ lifts $O\in\mathcal O$ of the same $\overline{w}$-weight. This proves Equation (5) and concludes the proof.

Second step. We reduce the blown-up matching polynomial to the blown-up perfect matching polynomial.

Proof. Put $n:=\sum_{i=1}^{r}w_i$. Let $\lambda$ be a new variable and let $q$ be the polynomial obtained from $\operatorname{PerfMatch}_{r}^{(\mathbf w)}$ by substituting $\theta\leftarrow\lambda\theta+1$ for every edge variable $\theta$ of the blow-up graph, including the inter-block variables $x_{ij}$ and the intra-block variables $z_i$. To prove the lemma, we establish the identity

where, for even $m$, $(m-1)!!=(m-1)(m-3)\cdots1$ is the number of perfect matchings in $K_m$, with the convention $(-1)!!=1$. The reduction follows by summing over $k$ and performing interpolation on $\lambda$, similar to Lemma A.7.

To prove Equation (9), let $Q_r^{(\mathbf w)}$ be the multigraph with, for each pair of vertices $u,v$, one “original” edge of weight $\lambda\theta_{uv}$ and one “neutral” edge of weight $1$, where $\theta_{uv}$ is the corresponding inter-block or intra-block variable.

Every $k$-matching $M$ in $K_r^{(\mathbf w)}$ can be extended to exactly $(n-2k-1)!!$ perfect matchings in $Q_r^{(\mathbf w)}$ by adding a perfect matching on neutral edges on the $n-2k$ vertices not matched by $M$. Each such extension has the same weight as $M$, up to a factor $\lambda^k$. The coefficient of $\lambda^k$ in $q$ sums over all such extensions of $k$-matchings in $K_r^{(\mathbf w)}$. □

We have collected both steps required to prove Lemma 3.1.

Proof of Lemma 3.1. Combine Lemma 3.4 and Lemma 3.5 with the transitivity of $c$-reductions via (2). □

Blown-Up Matching Polynomial to Monomial Symmetric Polynomials.

In this section, we extend ideas from [CLS22] to prove VNP-completeness of a large class of monomial symmetric polynomial families under $c$-reductions: if the defining partitions contain sufficiently many distinct parts and the number of variables is at least the degree, then the corresponding family of monomial symmetric polynomials is VNP-complete under $c$-reductions.

For a partition $\boldsymbol{\lambda}$ with degree $d(\boldsymbol{\lambda})$, define $m^{\mathrm{pow}}_{\boldsymbol{\lambda}}$ to be the unique polynomial in the power-sum variables $y_{1},\ldots,y_{d(\boldsymbol{\lambda})}$ such that, when the number of variables is at least $d(\boldsymbol{\lambda})$,

We now state the key lemma underlying our main result.

Proof. Write the partition $\boldsymbol{\lambda}$ as $\boldsymbol{\lambda} = (\mu_{1}^{w_{1}},\mu_{2}^{w_{2}},\ldots,\mu_{t}^{w_{t}})$, where $\mu_{1} > \mu_{2} > \cdots> \mu_{t} > 0$ are the distinct parts of $\boldsymbol{\lambda}$ and $w_{i}$ denotes the multiplicity of $\mu_{i}$ for each $i \in[t]$. By Corollary 2.5, there exists a sum-free Sidon subset $S_{0} \subseteq\{\mu_{1},\mu_{2},\ldots,\mu_{t}\}$ of size at least $0.04\sqrt{t}$. If necessary, remove one element from $S_{0}$ so that the total multiplicity of the remaining set is even, and call the resulting set $S$. For all sufficiently large $t$, this leaves $r := |S| > \alpha\sqrt{t}$ for a fixed constant $\alpha> 0$. Suppose we have

for some $1 \leq i_{1} < i_{2} < \cdots< i_{r} \leq t$.

$W := w_{i_{1}} + \cdots+ w_{i_{r}}$ is even. By Lemma A.6, we have

For brevity, let $\mathbf{y} = \{y_{1},y_{2},\ldots,y_{d(\boldsymbol{\lambda})}\}$. By definition of $m^{\mathrm{pow}}_{\boldsymbol{\lambda}}$ and Corollary 2.2, we have:

where $\lambda_{I} = \sum_{i\in I}\lambda_{i}$ for any nonempty $I \subseteq[k]$. We consider the homogeneous component of degree $k-W/2$ in $m^{\mathrm{pow}}_{\boldsymbol{\lambda}}$ and we substitute $y_{\mu_{i_{1}}} = y_{\mu_{i_{2}}} = \cdots= y_{\mu_{i_{r}}} = 0$ in this homogeneous component to obtain a new polynomial $g(\mathbf{y})$. Note that since $S$ is a sum-free Sidon set, this substitution cannot make any variable of the form $y_{\mu_{i_j}+\mu_{i_\ell}}$ vanish in $g(\mathbf{y})$. By Lemma A.7 we obtain:

Each summand in the above expansion of $m_{\lambda}^{\mathrm{pow}}$ corresponds to a partition $\mathcal{I}$ of the labelled positions $[k]$, and the degree of this summand is exactly $|\mathcal{I}|$. Thus a partition $\mathcal{I}$ contributes to $g(\mathbf{y})$ only if $|\mathcal{I}|=k-W/2$. Such a partition must contain at least $k-W$ singleton parts. Since we set

singletons corresponding to $\mu_{i_1},\ldots,\mu_{i_r}$ do not contribute. Hence every contributing partition $\mathcal{I}$ must contain exactly $k-W$ singleton parts corresponding to $\mu_j$ with $j\in[t]\setminus\{i_1,i_2,\ldots,i_r\}$.

After these $k-W$ forced singletons are fixed, the remaining $W$ elements are arranged into $W/2$ non-singleton parts. Since every non-singleton part has size at least two, all of these parts have size exactly two. Thus every remaining part pairs two elements from $S=\{\mu_{i_1},\ldots,\mu_{i_r}\}$, with $\mu_{i_j}$ appearing exactly $w_{i_j}$ times across these pairs. Because $S=\{\mu_{i_1},\ldots,\mu_{i_r}\}$ is a sum-free Sidon set, all sums

are distinct. Moreover, since $S$ is sum-free, none of these sums is equal to any element of $S$, so the substitution $y_{\mu_{i_1}}=\cdots=y_{\mu_{i_r}}=0$ does not delete a pair variable. It might still happen that $\mu_{i_j}+\mu_{i_\ell}=\mu_q$ for some $q\in[t]\setminus\{i_1,i_2,\ldots,i_r\}$. But all copies of $\mu_q$ outside $S$ occur as forced singletons, hence

divides $g(\mathbf{y})$.

Hence, using Lemma A.8, we can divide $g(\mathbf{y})$ by this monomial to obtain a new polynomial $h(\mathbf{y})$ such that:

Now, in $h(\mathbf{y})$, we perform the following substitutions for variables that occur:

• Each variable $y_{\mu_{i_j}+\mu_{i_k}}$ is substituted by a variable $x_{j,k}$ for $1\leq j<k\leq r$.

• Each variable $y_{2\mu_{i_j}}$ is substituted by a new variable $z_j$ for all $j\in[r]$.

This yields a polynomial $H$ in the variables $x_{i,j}$ for $1\leq i<j\leq r$ and $z_j$ for $j\in[r]$. From Equation (12) it follows immediately that

Combining Equation (10), Equation (12), and Lemma A.5, we obtain

Finally, observe that each surviving summand defining $H$ corresponds to a partition $\mathcal{I}$ of the labelled positions $[k]$ with exactly $W/2$ parts of size two arising from elements in $S$ with $\mu_{i_j}$ appearing $w_{i_j}$ many times. Hence each such partition corresponds to a perfect matching of the blow-up graph $K_{\mathbf{r}}^{(\mathbf{w})}$, and vice versa, by identifying the labelled positions carrying $\mu_{i_j}$ with the vertices of block $j$. This correspondence preserves monomial weights, and all surviving summands have the same nonzero coefficient because their partitions have the same number of parts, all of size one or two. See Figure 3 for a visualization. Therefore the polynomial $H$ is a nonzero scalar multiple of $\operatorname{PerfMatch}_{\mathbf{r}}^{(\mathbf{w})}$, where $\mathbf{w}=(w_{i_1},w_{i_2},\ldots,w_{i_r})$. Since we work over $\mathbb{C}$, this scalar can be inverted in the reduction. Hence $L_{\lambda}^{m}(x_1,\ldots,x_v)(\operatorname{PerfMatch}_{\mathbf{r}}^{(\mathbf{w})})$ is polynomially bounded in $v$ and $d(\lambda)$, which proves the lemma.

To prove our main result claimed in Theorem 1.1, we use the results proved in § 3.

Proof of Theorem 1.1. Let $(f_n)_{n\in\mathbb{N}}$ be a $p$-family of monomial symmetric polynomials. Write

for some partition $\lambda_n$ and positive integers $v_n$ with $v_n\ge d(\lambda_n)$ for all $n\in\mathbb{N}$. By assumption, $D(\lambda_n)\ge n^{\epsilon}$ for some constant $\epsilon>0$. The family $(f_n)$ is in VNP. Writing $\lambda_n=(\mu_1^{w_1},\ldots,\mu_t^{w_t})$, consider the product

which is a VP family (and hence a VNP family), since $v_n$, $t$, and $d(\lambda_n)$ are polynomially bounded for a $p$-family. The coefficient of $y_1^{w_1}\cdots y_t^{w_t}$ in this product is exactly $f_n$. By the standard closure of VNP under taking coefficients of monomials in polynomially many auxiliary variables [5 Theorem 2.19(3)], $(f_n)$ is a VNP family.

By Lemma 4.1, there exist constants $\alpha>0$ and $n_0$, and, for each $n\ge n_0$, parameters $r_n>\alpha\sqrt{D(\lambda_n)}$ and a vector $\mathbf{w}_n\in\mathbb{Z}_{>0}^{r_n}$ with even total sum such that

Since $D(\lambda_n)\ge n^\epsilon$, we have $r_n>\alpha n^{\epsilon/2}$. By Lemma 3.1, setting $s_n=2\lfloor r_n/4\rfloor$, we obtain

Composing the two reductions via Lemma A.5 yields

Thus $s_n\ge cn^{\epsilon/2}$ for some constant $c>0$ and all sufficiently large $n$. To reduce an arbitrary even-size perfect matching polynomial $\operatorname{PerfMatch}_m$ to the family $(f_n)$, choose an index $N=\max\{n_0,\lceil(m/c)^{2/\epsilon}\rceil\}$. Then $s_N\ge m$, and $\operatorname{PerfMatch}_m$ is a projection of $\operatorname{PerfMatch}_{s_N}$ by fixing the extra $s_N-m$ vertices to a predetermined perfect matching of weight 1 and setting all other incident extra edges to 0. Since $N$ is polynomially bounded in $m$, the perfect matching family $c$-reduces to $(f_n)$. The perfect matching polynomial family is VNP-complete under $p$-projections, hence $(f_n)_{n\in\mathbb{N}}$ is VNP-hard under $c$-reductions. Together with membership in VNP, this proves VNP-completeness. $\square$

Conclusion and Open Problems.

We have established an almost-complete dichotomy for the algebraic complexity of monomial symmetric polynomials in terms of the number of distinct parts in the partition $\lambda$. In our proofs, we introduced the blow-up matching polynomial and showed its hardness under arbitrary blow-ups with an even total number of vertices; this may be of independent interest toward robust hardness proofs of perturbed versions of VNP-hard problems. Our results suggest several directions for future work.

Removal of variable count restriction: All our lower bounds and VNP-hardness results require that the number of variables in the monomial symmetric polynomial is at least its degree. Can we show a lower bound for the case when the number of variables is smaller than the degree? This requirement arises because we rely on the algebraic independence of power symmetric polynomials via Theorem A.2, which only holds when $n\ge d(\lambda)$. Removing this constraint would significantly strengthen our results and extend the dichotomy to a broader class of monomial symmetric polynomials. For a concrete example, consider the Vandermonde permanent

This family is not covered by our results, since it has only $n$ variables but degree $\binom{n+1}{2}$. It is a natural open problem whether the Vandermonde permanent family is VNP-complete.

Fine-grained complexity in the middle regime: What is the complexity of the monomial symmetric polynomial family $m_\lambda$ when the number of distinct parts in $\lambda$ is $\omega(1)$ but lies outside the range covered by our hardness theorem, e.g., $\operatorname{poly}(\log n)$? Can we show a lower bound for this case? Treating the number of distinct parts as a parameter might be useful; parameterized complexity was introduced in algebraic complexity by [2].

For immanants, Curticapean [Cur21] has shown such a fine-grained result: If a certain parameter is bounded by a constant, then the corresponding immanant family is in VP, whereas unbounded growth places it outside VP, assuming VFPT $\ne$ VW[1]. In a similar spirit, can we for instance show that $m_\lambda$ is fixed parameter tractable when parameterized by the number of distinct parts in $\lambda$, without requiring any restriction on the number of variables? This would provide a more nuanced understanding of the complexity landscape beyond the dichotomy.

Background.

Symmetric Polynomials.

An alternative set of algebraically independent generators is provided by the power sum symmetric polynomials. The following theorem follows from the Newton identities, which relate the power sum symmetric polynomials to the elementary symmetric polynomials; see [17].

Algebraic Complexity Classes and Reductions.

In algebraic complexity theory, reductions between polynomials are typically defined via projections. A polynomial $f \in\mathbb{F}[x_1,x_2,\ldots,x_n]$ is said to be a projection of another polynomial $g \in\mathbb{F}[y_1,y_2,\ldots,y_m]$ if $f$ can be obtained from $g$ by substituting each variable $y_i$ with either a variable $x_j$ or a constant from the field $\mathbb{F}$. This notion of reduction is quite restrictive, since it does not allow adaptive computations or multiple queries to the polynomial being reduced to.

A more flexible notion is given by $c$-reductions. To define it, we introduce the oracle complexity of a polynomial. The oracle complexity of a polynomial $f$ with respect to another polynomial $g$ is the minimum size of an arithmetic circuit computing $f$ that is allowed to query an oracle for $g$. Following the notation of [CLS22], we denote this quantity by $L^{g}(f)$. If $L^{g}(f)$ is polynomially bounded in the number of variables and degree of $f$ and $g$, we simply write $f \leq_c g$ to simplify the notation. Throughout the paper, the complexity notation $\widetilde{O}$ hides polylogarithmic factors.

Now we define the notion of VNP-completeness under $c$-reductions. A sequence $(u)=(u_n)_{n\in\mathbb{N}}$ of non-negative integers is called $p$-bounded if there exists a polynomial function $p$ such that for all $n\in\mathbb{N}$, we have $u_n \leq p(n)$.

A sequence $(f_n)_{n\in\mathbb{N}}$ of polynomials is called a $p$-family if the sequences of variable counts and degrees are $p$-bounded.

A $p$-family $(f_n)_{n\in\mathbb{N}}$ is $c$-reducible to $(g_n)_{n\in\mathbb{N}}$, denoted by $(f_n) \preceq_c (g_n)$, if there exists a $p$-bounded sequence $(t_n)_{n\in\mathbb{N}}$ such that $L^{g_{t_n}}(f_n)$ is $p$-bounded. It is well known that the permanent polynomial family $(\operatorname{Per}_n)_{n\in\mathbb{N}}$ defined as

is VNP-complete under $c$-reductions. In fact, $(\operatorname{Per}_n)_{n\in\mathbb{N}}$ is VNP-complete under the more restrictive notion of $p$-projections, which is a special case of $c$-reductions where the reduction is given by a single substitution of variables. The following lemma is an immediate consequence of the definition of $c$-reductions.

Tools From Algebraic Complexity Theory.

Corollary 2.2 expresses the monomial symmetric polynomial $m_\lambda$ as a polynomial in the power sum symmetric polynomials. Assume that the number of variables $n$ is at least the degree of $m_\lambda$, i.e., $n \geq d(\lambda)$. Then by Theorem A.2, the power sum symmetric polynomials $p_1,p_2,\ldots,p_n$ are algebraically independent and generate the ring of symmetric polynomials. Theorem 4 of [3], together with the efficient Newton identities, implies that the arithmetic complexity of $m_\lambda^{\mathrm{pow}}$ with respect to the oracle $m_\lambda$ is quite small. This result is stated more explicitly in [CKL+23], Theorem 4.16.

These results prove a more general statement: for any symmetric polynomial, the complexity of expressing it as a polynomial in the power sums is small relative to an oracle for the original polynomial. The above lemma is the special case corresponding to monomial symmetric polynomials.

We will also need the following folklore result concerning the arithmetic complexity of homogeneous components of polynomials. For a polynomial $f \in\mathbb{F}[x_1,\ldots,x_n]$ and a non-negative integer $m$, we denote by $\operatorname{Hom}_m(f)$ the homogeneous component of $f$ of degree $m$, i.e., the sum of all monomials in $f$ that have total degree $m$.

We also need a result on the arithmetic complexity of dividing polynomials by a monomial factor. This follows immediately from results in [Str73,Kal86,Kal87,Kal85,Kal89], but we give a self-contained proof below for completeness.

Proof. Suppose $f \in\mathbb{F}[x_1,\ldots,x_n]$ is a polynomial of degree $d$. Suppose $m$ is a monomial factor of $f$. Then $f=gm$, where $g$ is a polynomial of degree at most $d$. Define $f_{\mathrm{shift}}(x):=f(x_1+1,\ldots,x_n+1)$ and $g_{\mathrm{shift}}(x):=g(x_1+1,\ldots,x_n+1)$. The oracle for $f$ computes $f_{\mathrm{shift}}$ by querying $f$ at the shifted inputs. This substitution does not change the degree of the polynomial, so $f_{\mathrm{shift}}$ is still a polynomial of degree $d$. Moreover, under this substitution, the monomial $m$ is mapped to a polynomial of the form $1-h$ with constant term of $h$ being zero. The polynomial $h$ is explicitly computable from the monomial $m$, and hence so are its powers. Thus we can write $f_{\mathrm{shift}}=g_{\mathrm{shift}}(1-h)$. Now we have $g_{\mathrm{shift}}=f_{\mathrm{shift}}/(1-h)=f_{\mathrm{shift}}(1+h+h^2+\cdots)$. We use $F$ to denote the polynomial $f_{\mathrm{shift}}(1+h+h^2+\cdots+h^d)$. Note that $g_{\mathrm{shift}}$ is a polynomial of degree at most $d$, hence we have:

Indeed, $F=g_{\mathrm{shift}}(1-h^{d+1})$, and the term $g_{\mathrm{shift}}h^{d+1}$ has no homogeneous component of degree at most $d$ because $h$ has zero constant term. Since $\deg(F)=O(d^2)$, the sum of the homogeneous components of $F$ of degree at most $d$ can be recovered by the usual interpolation in an auxiliary scaling variable using polynomially many evaluations of $F$. Finally substituting $x_i \leftarrow x_i-1$ recovers $g$ from $g_{\mathrm{shift}}$. Thus $L^f(g)\le\operatorname{poly}(n,d)$.

Omitted Proofs.

Proof sketch of Theorem 1.2. Let $\lambda=(\mu_1^{w_1},\mu_2^{w_2},\ldots,\mu_t^{w_t})$ be a partition with at most $t$ distinct parts. Then the monomial symmetric polynomial $m_\lambda$ can be written as the coefficient of $y_1^{w_1}y_2^{w_2}\cdots y_t^{w_t}$ in the polynomial $G$ defined below:

Note that the individual degree of each $y_j$ in $G$ is at most $n$. We now think of $G$ as a polynomial in the variables $y_1,y_2,\ldots,y_t$ with coefficients in $\mathbb{F}[x_1,x_2,\ldots,x_n]$. We use the well-known Kronecker substitution and replace $y_i$ by $y^{(n+1)^{i-1}}$ for all $i \in[t]$ to obtain a univariate polynomial $H(y)$ in $y$ with coefficients in $\mathbb{F}[x_1,x_2,\ldots,x_n]$. This mapping ensures that each monomial $y_1^{a_1}y_2^{a_2}\cdots y_t^{a_t}$ of $G$ is mapped to a unique monomial $y^{a_1+a_2(n+1)+\cdots+a_t(n+1)^{t-1}}$ of $H(y)$. Define

In particular, the monomial $y_1^{w_1}y_2^{w_2}\cdots y_t^{w_t}$ is mapped to $y^W$. Hence, we can extract the coefficient of $y^W$ in $H(y)$ to obtain $m_\lambda$. Since the degree of $H(y)$ is at most $(n+1)^t-1$, we can evaluate $H(y)$ at $(n+1)^t$ many points and interpolate to extract the coefficient of $y^W$. For one evaluation point $\alpha\in\mathbb{F}$, computing all powers $x_i^{\mu_j}$ with $\mu_j \le d$, forming the $n$ factors, and multiplying them costs $O(nt \cdot\operatorname{poly}(d))$ gates. Since $\lambda$ is a partition of degree $d$ into positive parts, we have $t \le d$, so this per-point cost is at most $n \cdot\operatorname{poly}(d)$. The $(n+1)^t = n^{O(t)}$ interpolation points and final linear combination give the claimed $\operatorname{poly}(d) \cdot n^{O(t)}$ bound.

Proof of Lemma 3.2.

Recall that the matching-generating polynomial of $H$ is $M(H,x) := \sum_k m_k x^k$. Throughout this section, fix $1 \le b \le a$ and abbreviate

By definition,

so $\deg f = b$, $\deg g \le b$, and $f(0) = g(0) = 1$. Moreover $f \not\equiv g$, for instance because the coefficient of $x$ is $ab$ in $f$ and $(a-1)b$ in $g$.

We will use the standard relation between matchings in complete bipartite graphs and generalized Laguerre polynomials. For $\alpha> -1$,

A direct coefficient comparison gives

By [Sze75, Section 5.1, (5.1.1)], $L_n^{(\alpha)}$ is orthogonal on $[0,\infty)$ with weight $e^{-x}x^\alpha$ for $\alpha> -1$. Since $a-b \ge0$, Szegő’s zero theorem [Sze75, Theorem 3.3.1] implies that $L_b^{(a-b)}$ has $b$ distinct positive real zeros. Hence the roots of $f = M(K_{a,b},x)$ are simple and nonzero.

Proof of $Lemma\ 3.2$. The preceding discussion shows that $f$ has $b$ distinct nonzero roots. If $g$ vanished on all these roots, then $f$ and $g$ would agree on $b+1$ points, namely on $0$ and the $b$ roots. This would imply $f \equiv g$, because $f$ and $g$ are of degree at most $b$, contradicting $f \not\equiv g$. It follows that there is a root $\xi$ of $f$ that is not a root of $g$; this is our desired value $\xi= \xi(a,b)$.