2026-10-11T04:21:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25333 2026-03-19T12:03:39Z ddc:004 open_access

Symmetric Algebraic Circuits and Homomorphism Polynomials Dawar, Anuj Pago, Benedikt Seppelt, Tim algebraic complexity finite model theory symmetric circuits homomorphism counting graph homomorphism treewidth counting width first-order logic with counting quantifiers The central open question of algebraic complexity is whether VP ≠ VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020), who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Benedikt Pago and Tim Seppelt 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.46 urn:nbn:de:0030-drops-253330 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.46 eng https://creativecommons.org/licenses/by/4.0/legalcode