Characterizing Small Circuit Classes from ๐…๐€๐‚ 0 \mathbf{FAC}^{0} to ๐…๐€๐‚ 1 \mathbf{FAC}^{1} via Discrete Ordinary Differential Equations

Melissa Antonelli, Arnaud Durand, Juha Kontinen ยท 2025

Read Characterizing Small Circuit Classes from ๐…๐€๐‚ 0 \mathbf{FAC}^{0} to ๐…๐€๐‚ 1 \mathbf{FAC}^{1} via Discrete Ordinary Differential Equations by Melissa Antonelli, Arnaud Durand, Juha Kontinen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-23404.txt.

Introduction

Melissa Antonelli, Arnaud Durand, and Juha Kontinen connect two distant areas in this two thousand twenty-five theoretical computer science paper. On one side sit small circuit classes, families of functions computed by shallow circuits. On the other sit discrete ordinary differential equations, used as recursion schemes for defining functions. Recent work captured polynomial-time functions and then the constant-depth class FAC-zero through such equation-based schemas.

The authors build a uniform framework extending those characterizations across several small circuit classes, up to FAC-one. Restrictions on linearity and on growth rates of the functions involved correspond exactly to the different classes. They also prove completeness results, including the first equation-based characterizations for constant-depth circuits with modulo-two gates and for logarithmic-depth bounded fan-in circuits. The link may give new tools for proving bounds in the circuit hierarchy.

Catalog record

CREATORMelissa Antonelli, Arnaud Durand, Juha Kontinen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-23404

Browse the full library ยท About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterizing Small Circuit Classes from ๐…๐€๐‚ 0 \mathbf{FAC}^{0} to ๐…๐€๐‚ 1 \mathbf{FAC}^{1} via Discrete Ordinary Differential Equations Melissa Antonelli, Arnaud Durand, Juha Kontinen Abstract In this paper, we provide a uniform framework for investigating small circuit classes and bounds through the lens of ordinary differential equations (ODEs). Following an approach recently introduced to capture the class of polynomial-time computable functions via ODE-based recursion schemas and later applied to the context of functions computed by unbounded fan-in circuits of constant depth ( ๐…๐€๐‚ 0 \mathbf{FAC}^{0} ), we study multiple relevant small circuit classes. In particular, we show that natural restrictions on linearity and derivation along functions with specific growth rate correspond to kinds of functions that can be proved to be in various classes, ranging from ๐…๐€๐‚ 0 \mathbf{FAC}^{0} to ๐…๐€๐‚ 1 \mathbf{FAC}^{1} . This reveals an intriguing link between constraints over linear-length ODEs and circuit computation, providing new tools to tackle the complex challenge of establishing bounds for classes in the circuit hierarchies and possibly enhancing our understanding of the role of counters in this setting. Additionally, we establish several completeness results, in particular obtaining the first ODE-based characterizations for the classes of functions computable in constant depth with unbounded fan-in and Mod 2 gates ( ๐…๐€๐‚๐‚ โก [ ๐Ÿ ] \mathbf{FACC[2]} ) and in logarithmic depth with bounded fan-in Boolean gates ( ๐…๐๐‚ 1 \mathbf{FNC}^{1} ). 1 Introduction Implicit computational complexity is a active area of theoretical computer science that aims to provide machine-independent characterizations of relevant complexity classes. In the context of recursion theory, a foundational work in this field is by Cobham [ 17 ] , who, in the 1960s, provided an implicit characterization of the class of polynomial-time computable functions ( \mathbf{FP} ) through a limited recursion schema. This work not only led to the development of function algebras characterizing multiple classes different from poly-time (see [ 14 ] ), but also inspired several alternative recursion-theoretic approaches [ 5 , 27 , 29 ] . Among them, the one introduced in [ 9 ] , shows that ordinary differential equations (ODEs) provide a natural tool for algorithmic design and offers an original characterization of \mathbf{FP} , using linear systems of equations and derivation along a logarithmically growing function (such as the length function \ell ). Informally, the latter condition controls the number of recursion steps, while linearity governs the growth of objects generated during the computation. This approach has recently been generalized to the continuous setting [ 6 , 7 ] and to the study of two small circuit classes [ 2 ] . In this paper, we extend the latter far further by presenting a comprehensive investigation of small circuit classes through the lens of ODE schemas. Although small circuit classes have been characterized in different ways, investigating them through the ODE framework has never been attempted (except for [ 2 ] ). This approach is both interesting , as for a descriptive method based on ODEs to be meaningful and fruitful, it must be able to adjust with very subtle changes in restricted models of computation, and challenging , because even simple and useful mathematical functions may not be computable within the considered classes and, consequently, the tools available may seem drastically restricted and the naturalness of the approach questionable. However, the results of this paper show that this is not hopeless. Very simple and natural restrictions on linearity โ€“ namely, constraining the values of coefficients and allowing (or not) the call for the sign of the defined function inside the linear term โ€“ and on the function along which derivation is performed, allows us to capture the very essence of small circuit computation. Many classical functions โ€“ such as polylog bit sum, parity, majority, iterated sum and product, and binary search โ€“ are shown to be naturally encapsulated in very simple linear ODE families. For this reason, we believe that our approach to this line of research, which is still in its beginning, can shed some new light on circuit computation and offer a simple (and machine-independent) framework for analyzing these notoriously hard problems through very natural and uniform constraints on linear ODEs. Concretely, the results of this paper have led to completely original ODE-based characterizations for the classes of functions computable by unbounded fan-in circuits of constant depth and polynomial size that allow Mod 2 gates ( \mathbf{FACC[2]} ) and by bounded fan-in circuits of logarithmic depth and polynomial size ( \mathbf{FNC}^{1} ). We have also improved our understanding of schemas capturing the classes of functions computable by unbounded fan-in circuits of constant depth and polynomial size ( \mathbf{FAC}^{0} ), possibly including Maj gates ( \mathbf{FTC}^{0} ), by generalizing and making them part of a more general picture. Finally, we have shown that considering schemas with derivative along \ell_{2}=\ell\circ\ell is definitely worth investigating: in particular, the corresponding linear schema is in \mathbf{FNC}^{1} , somewhat mirroring what \ell -ODE does for \mathbf{FP} . Structure of the paper. In Section 2 , we present the basics of the method developed in [ 9 ] , the necessary notions to formulate our results, and recap definitions of the small circuit classes we will consider throughout the paper. In Section 3 , we present, in a high-level yet systematic and uniform manner, the main schemas (differently) corresponding to the classes that will be studied. In Section 4 , we introduce ODE-based schemas obtained by deriving along \ell and imposing different constraints on linearity, and we show that they are computable in the respective circuit classes. We also provide improved completeness results for \mathbf{FAC}^{0} and \mathbf{FTC}^{0} , along with completely original ODE-based characterizations for \mathbf{FACC[2]} and \mathbf{FNC}^{1} . In Section 5 , we introduce a new class of ODE schemas, the defining feature of which consists of deriving along \ell_{2} . Our main result here is introduction of a very natural linear \ell_{2} -ODE the computation of which can be performed in \mathbf{FNC}^{1} . We conclude in Section 6 pointing to possible directions for future research. For space reasons, most proofs are omitted or only sketched in the paper, but full details can be found in the Appendix. To make the exposition shorter, most of our characterizations are proved indirectly, as these proofs tend to be more compact. However, direct proofs (both in the uniform and non-uniform settings) can be provided (but are not presented here). 2 Preliminaries We assume the reader familiar with the basics of complexity theory. In this section, we briefly introduce the approach to complexity delineated in [ 10 ] (see the original paper for full details) and a few notions needed for our new characterizations. We also cursorily recall the definitions of the circuit classes that we will consider in the remainder of the paper. 2.1 Capturing Complexity via ODEs One of the main approaches developed in implicit computational complexity is that based on recursion. It was initiated by Cobham [ 17 ] , who gave the first characterization for \mathbf{FP} via a limited recursion schema. This groundbreaking result has inspired not only similar characterizations for other classes, but also alternative recursion-based approaches to capture poly-time computable functions, such as safe recursion [ 5 ] and ramification [ 27 , 28 ]

Read the complete text