2026-07-21T15:08:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26550 2026-07-01T07:16:15Z ddc:004 open_access

Recursion and Proof Theoretical Characterizations of Small Circuit Classes with Modulo Counting via Discrete Differential Equations Antonelli, Melissa Durand, Arnaud Li, Rui Implicit complexity circuit complexity small circuit classes with counting discrete ODEs recursion theory bounded arithmetic The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a constant through the lens of discrete ordinary differential equations (ODEs). So far, recursion-theoretic characterizations have been provided for functions computed by circuits of constant depth, including gates counting modulo 2 and 6 only (i.e., for the classes FAC⁰[2] and FAC⁰[6], resp.). In this paper, it is shown that considering ODE schemas, rather than bounded recursion, allows for a more fine-grained analysis, leading to (uniform) characterizations for all classes FAC⁰[n] (n ∈ ℕ), i.e. functions computed by circuits including counting modulo n gates. Inspired by the syntactic form of the ODE schemas, we go further in this direction and present first-order bounded theories for capturing provably total functions in each of these classes. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Melissa Antonelli and Arnaud Durand and Rui Li 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.162 urn:nbn:de:0030-drops-265501 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.162 eng https://creativecommons.org/licenses/by/4.0/legalcode