2026-08-01T06:27:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17408 2024-03-06T10:59:40Z ddc:004 open_access

On the VNP-Hardness of Some Monomial Symmetric Polynomials Curticapean, Radu Limaye, Nutan Srinivasan, Srikanth algebraic complexity symmetric polynomial permanent Sidon set A polynomial P ∈ 𝔽[x_1,…,x_n] is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, especially in algebraic complexity theory. In this paper, we prove the computational hardness of one of the most basic kinds of symmetric polynomials: the monomial symmetric polynomials, which are obtained by summing all distinct permutations of a single monomial. This family of symmetric functions is a natural basis for the space of symmetric polynomials (over any field), and generalizes many well-studied families such as the elementary symmetric polynomials and the power-sum symmetric polynomials. We show that certain families of monomial symmetric polynomials are VNP-complete with respect to oracle reductions. This stands in stark contrast to the case of elementary and power symmetric polynomials, both of which have constant-depth circuits of polynomial size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radu Curticapean and Nutan Limaye and Srikanth Srinivasan 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.16 urn:nbn:de:0030-drops-174081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode