2026-07-23T18:55:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3424 2024-03-06T10:34:12Z ddc:004 open_access

Monomials in arithmetic circuits: Complete problems in the counting hierarchy Fournier, Hervé Malod, Guillaume Mengel, Stefan arithmetic circuits counting problems polynomials We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems before. We also study these questions for circuits computing multilinear polynomials. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hervé Fournier and Guillaume Malod and Stefan Mengel 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.362 urn:nbn:de:0030-drops-34240 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.362 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode