{"id":"arxiv/2610.25181","url":"https://arxiv.org/abs/2610.25181","tags":["cs.CC","cs.SC","math.CO"],"score":0,"title":"When Are Monomial Symmetric Polynomials Hard?","domain":"cs.CC","source":"arxiv","authors":["Markus Bläser","Radu Curticapean","Sagnik Dutta","Gorav Jindal"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-18","reactions":{}}