2026-07-24T14:30:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25159 2026-02-09T08:18:01Z ddc:004 open_access

Uniformity Within Parameterized Circuit Classes Hegeman, Steef Martens, Jan Laarman, Alfons Parameterized complexity circuit complexity uniformity descriptive complexity We study uniformity conditions for parameterized Boolean circuit families. Uniformity conditions require that the infinitely many circuits in a circuit family are in some sense easy to construct from one shared description. For shallow circuit families, logtime-uniformity is often desired but quite technical to prove. Despite that, proving it is often left as an exercise for the reader - even for recently introduced classes in parameterized circuit complexity, where uniformity conditions have not yet been explicitly studied. We formally define parameterized versions of linear-uniformity, logtime-uniformity, and FO-uniformity, and prove that these result in equivalent complexity classes when imposed on para-AC⁰ and para-AC^{0↑}. Overall, we provide a convenient way to verify uniformity for shallow parameterized circuit classes, and thereby substantiate claims of uniformity in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steef Hegeman and Jan Martens and Alfons Laarman 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.27 urn:nbn:de:0030-drops-251598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode