Search Results

Documents authored by Li, Rui

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2026.162
Recursion and Proof Theoretical Characterizations of Small Circuit Classes with Modulo Counting via Discrete Differential Equations

Authors: Melissa Antonelli, Arnaud Durand, and Rui Li

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
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.
Cite as

Melissa Antonelli, Arnaud Durand, and Rui Li. Recursion and Proof Theoretical Characterizations of Small Circuit Classes with Modulo Counting via Discrete Differential Equations. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 162:1-162:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{antonelli_et_al:LIPIcs.ICALP.2026.162,
  author =	{Antonelli, Melissa and Durand, Arnaud and Li, Rui},
  title =	{{Recursion and Proof Theoretical Characterizations of Small Circuit Classes with Modulo Counting via Discrete Differential Equations}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{162:1--162:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.162},
  URN =		{urn:nbn:de:0030-drops-265501},
  doi =		{10.4230/LIPIcs.ICALP.2026.162},
  annote =	{Keywords: Implicit complexity, circuit complexity, small circuit classes with counting, discrete ODEs, recursion theory, bounded arithmetic}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact