Boolean and arithmetic circuits are receiving increasing attention in AI. In particular, due to the connection with neural networks, the evaluation of their computational resources, as studied in circuit complexity, has been thoroughly investigated to address concrete issues, such as scalability. In this paper, we outline an original approach to explore this area using recursion schemas defined by discrete ordinary diferential equations (ODEs). Relying on them, we provide new characterisations of various small circuit classes, ofering a uniform and comprehensive framework to potentially unveil the relationships between them and clarify notions like counting in this context. Here, we present a systematic and integrated overview of the main results obtained thus far, namely the introduction of algebras characterised by diferent constraints on the linearity defining their ODE schemas and capable of capturing function classes that range from those computed by unbounded fan-in circuits working in constant depth (FAC0) to bounded Boolean circuits working in logarithmic depth (FNC1), including those with majority (FTC0) and counting modulo 2 gates (FACC[2]). This would provide a starting point for discussing the various ongoing directions of this research and the potential challenges associated with this new perspective on the study of circuit complexity.
In recent decades, Boolean and arithmetic circuits have received increasing attention not only in
traditional fields of computer science, such as database theory and communication complexity, but
also in multiple areas of AI, from reinforcement learning and Bayesian networks to language and ML
models [
Within this framework, we aim to provide an original viewpoint for investigating circuit complexity and enhancing the understanding of the relationship between small circuit classes and with arithmetic circuits. In this paper, we present an (integrated) overview of the main results achieved so far by generalising the approach introduced in [9], which captures functions computable in polynomial time (FP) using discrete ordinary diferential equations (ODEs), to the study of circuit complexity. Indeed, although small circuit classes have been characterised in diferent ways, investigating them through ODEs has only been attempted very recently [10, 11, 12]. In particular, it has emerged that, by slightly modifying the ODE-based schema characterising FP, we can perform computations in (and, in several cases, characterise) multiple function classes, ranging from those computed by Boolean circuits with unbounded fan-in working in constant depth (FAC0) to those working in logarithmic depth (FAC1). This approach has also been proven to be strikingly natural: by applying simple restrictions on linearity, and performing derivation along functions of specific growth rate, we can capture the essence of small circuit computation. Additionally, many classical functions – from poly-log bit sum to parity and majority, from iterated sum and product to binary search – are shown to be easily encapsulated in linear ODE families. Accordingly, we believe that this new line of research, which is still in its early stages, can shed light on circuit computation and ofer a simple, machine-independent framework for analysing notoriously hard problems and bounds in terms of natural and uniform constraints on linear ODEs. The goal of this work is to provide a comprehensive overview that includes and compares the key results achieved thus far (even considering a few new schemas not appearing in [10, 11, 12], e.g. ℓ-sODE), as well as to discuss challenges and future research directions.
Implicit computational complexity is an active area of theoretical computer science that aims to provide machine-independent characterisations of relevant complexity classes. Specifically, one of the foundational results in the area of recursion theory was established by Cobham [13], who captured FP relying on a restricted recursion schema called bounded recursion on notation (BRN) and such that (0, y) = (y) (, y) ≤ (, y) ((), y) = ℎ(, y, (, y)) ̸= 0 for ∈ {0, 1}. In BRN, the growth of the defined function is controlled by another function (to be in FP), while the number of induction steps is kept under control by the application of the binary successor functions () = 2 + , ∈ {0, 1}. However, such a schema is in a sense not fully satisfactory as it imposes an explicit bound on recursion in the form of an already known function. Accordingly, Cobham’s seminal work not only led to a variety of implicit characterisations for classes other than FP, but also inspired alternative approaches to capture this class, e.g. relying on safe recursion [14] and ramification [ 15, 16]. Among them, the proposal by [9] has the advantage of neither imposing any explicit bound on the recursion schema nor assigning specific roles to variables. Indeed, it is based on special discrete ODEs, which combine two peculiar features: derivation along specific functions , so to control the number of computation steps, and linearity, namely a syntactic form of the equation allowing to control the object size.
Recall that the discrete derivative of f () is defined as Δf () = f ( + 1) − f () and that ODEs are expressions of the form: f (, y) = h(︀ , y, f (, y))︀
where f(,y) stands for the derivative of f (, y) considered as a function of , for y fixed. When some initial value f (0, y) = (y) is added, this is called Initial Value Problem (IVP).
Notation 1. Let sg : Z → Z be the sign function over Z, taking value 1 for > 0 and 0 otherwise; let cosg : Z → Z be the cosign function such that cosg() = 1 − sg().
A (limited) sg-polynomial expression (1, . . . , ℎ) is an expression built over the signature {+, − , ×} ({+, −} , resp.), the function sg and a set of variables = {1, . . . , ℎ}, plus integer constants. A sg-polynomial expression is said to be essentially linear in a set of variables x, if there are sg-polynomial expressions 1, 2 such that it is of the form 1 × + 2, and occurs in 1, 2 only under the scope of the sign function. The concept of linearity allows to control the growth of functions defined by ODEs.
Notation 2. We use ℓ() to denote the length function, returning the length of written in binary. Formally, it is defined as ℓ(0) = 0 and ℓ() = ⌈log2( + 1)⌉.
In what follows, we will consider functions f : N+1 → Z, i.e. vectors of functions f = 1, . . . , from N+1 to Z and introduce the linear ℓ-ODE schema, obtained by deriving along the length function ℓ. Definition 1 (Linear ℓ-ODE). Given g, h, u and , the function f is said to be linear -ODE definable from g, h and u if it is the solution of the IVP with initial value f (0, y) = g(y) and such that: f (, y)
= u(︀ , y, h(, y), f (, y))︀ , with u essentially linear in f (, y). If = ℓ, this schema is called linear length-ODE, ℓ-ODE. Intuitively, one of the key properties of -ODE is its dependence on the number of distinct values of , i.e. that the value of f (, y) changes only when the value of (, y) does. Moreover, if u is essentially linear in f (, y), as linear length-ODE is, there exist matrices A and B, such that f (0, y) = g(y) and f(,y) = A︀( , y, h(, y), f (, y))︀ × f (, y) + B(, y, h(, y), f (, y)). Then, for all and y, the ℓ solution f (, y) defined by linear ℓ-ODE is as follows: ℓ(∑)︁−1 ︂( ℓ(∏)︁− 1 (︁ =− 1 =+1
1 + A( (), y, h( (), y), f ( (), y))︀ ︁) )︂ × B︀( (), y, h( (), y), f ( (), y))︀ , where () = 2 − 1 denotes the greatest integer whose length is (see [17] for further details). Example 1 (Function 2ℓ()). The function ↦→ 2ℓ() can be rewritten as the solution of the IVP with initial value (0) = 1 and such that () = (), i.e. a restricted case of linear ℓ-ODE with = 1 and ℓ = 0; that is, () = ∏︀ℓ(=0)− 1 2 = 2ℓ().
One of the main results of [9] is the characterisation of FP by the algebra made of basic functions 0, 1, sg, ℓ, +, − , × and the projection function and closed under composition (∘ ) and ℓ-ODE:
LDL = [0, 1, ℓ, sg, +, − , ; ∘ , ℓ-ODE].
In this section we present an overview of the characterisations of small circuit classes obtained by relying on diferent (strict and non-strict) ℓ-ODE schemas defined by imposing natural constraints on the linearity allowed by linear length-ODE.1 This investigation has already demonstrated a strong link between depth constraints in circuit computation and the syntactical constraints that define corresponding linear length ODEs. In particular, it has emerged that strict schemas, i.e., schemas defined by ODEs not involving calls to (, y) occurring under the scope of the sign function, are linked to constant-depth circuit computation, possibly including counting. While constant-depth classes can be fully captured due to them, it seems that a similar strict characterisation is not feasible for larger classes. Indeed, full and strict linear computation along ℓ is in FTC0. Additionally, some constraints over (non-strict) schemas have emerged to be particularly interesting in the small circuit setting, namely taking values 1 or –1, taking only values 0 or 1 or being strictly positive, and (, y) occurring under the scope of the sign function only in expressions of the form (, y) − , for ∈ N. Notation 3. An equation and, by extension, an ODE schema is said to be strict when it does not include any call to (, y) in or , not even under the scope of the sign function; a call to (, y) is said to be a simple if (, y) occurs in and only in expressions of the form = sg( (, y)). We use (, y) (resp., (, y, ℎ(, y), (, y))) for functions (resp., expressions) taking values in {0, 1}. 1Although here we focus on schemas obtained by deriving along the function ℓ, some upper bounds have also been shown for similar linear schemas obtained by deriving along ℓ2 = (ℓ ∘ ℓ) (see [12, Sec. 5]).
In [10], to deal with FAC0 computation, we introduced the following strict ℓ-ODE schemas: Definition 2 (Schemas ℓ-ODE1, ℓ-ODE3). Given : N → N and : N+1 → {0, 1}, the function : N+1 → N is obtained by ℓ-ODE1 from and , if it is the solution of the IVP defined by (0, y) = (y) and such that: (, y)
= (, y) + (, y).
ℓ Analogously, is defined by ℓ-ODE3 from if it is the solution of the IVP defined by (0, y) = (y) and (, y) ℓ = − ︂⌈ (, y) ⌉︂ 2 .
Intuitively, ℓ-ODE1 corresponds to iteratively left-shifting (the binary representation of) a given number, possibly adding 1, while ℓ-ODE3 defines basic right-shifting computation. Notably, the latter schema is enough to encode the function BIT(, ), computing the ℓ()ℎ bit of . Relying on them we introduced the algebra below:
ACDL = [0, 1, ℓ, sg, +, − , ÷ 2, #, ; ∘ , ℓ-ODE1, ℓ-ODE3] and, due to it, characterise FAC0 [10, Theorem 18]. Notably, both existential and universal sharply bounded quantification, as well as minimisation can be naturally rewritten in ACDL. Remark 1 (Sharply Bounded Quantification and Minimisation) . Let ⊆ N+1 and ℎ be its characteristic function. Then, for all and y, it holds that where is the solution of the IVP: (∃ ≤ ℓ())(, y) = sg( (, y)) (0, y) = ℎ(0, y) (, y) ℓ
= (, y) + ℎ(ℓ( + 1), y) which is an instance of ℓ-ODE1. Intuitively, (, y) ̸= 0 when, for some smaller than ℓ(), (, y) is satisfied (i.e. ℎ(, y) = 1): if such instance exists, our bounded search ends with a positive answer.
Universally bounded quantification can be expressed in a similar way. Let’s consider cosg( (, y)) for defined substituting the value of ℎ with its co-sign. So, (∀ ≤ ℓ())(, y) = cosg( (, y)) and (0, y) = cosg(ℎ(0, y)) (, y) ℓ
= (, y) + cosg(ℎ(ℓ( + 1), y)).
Also sharply bounded -operator can be rewritten in ACDL via ℓ-ODE1. Let . (, y) returns the smallest ≤ ℓ() such that (, y). This can be rewritten as:
mu(, y) = ℓ() − ℓ( (, y)) where is the solution of the IVP below:
(0, y) = 0 (, y) ℓ
= (, y) + ∃ ≤ ℓ( + 1)(︀ ℎ(, y) = 1)︀ for ℎ ∈ {0, 1} being the characteristic function of (, y).
Additionally, the strict schema below is introduced to characterise FTC0: Definition 3 (Schema ℓ-ODE*2). Given : N → N, : N+1 → {0, 1} and ℎ : N → N, the function : N+1 → N is defined by ℓ-ODE*2 from , ℎ and when it is the solution of the IVP with initial value (0, y) = (y) and such that
(ℓ, y) = (︀ 2ℓ(ℎ(y)) − 1) × (, y) + (, y).
If we add the constraint that ℎ(y) ≥ 1, then ℓ-ODE*2 is called ℓ-ODE2. Notably, the latter schema is not only in FAC0, but, together with ℓ-ODE3 (or BIT), it is also enough to capture FAC0 without including # among the basic functions. In [12], an alternative, strict schema, called ℓ-pODE, is introduced to capture FTC0.
Definition 4 (Schema ℓ-pODE). Given : N → N and ℎ : N+1 → N, the function : N+1 → N is defined by ℓ-pODE from and ℎ, if it is the solution of the IVP with initial value (0, y) = (y) and (, y) ℓ
= (︀ , y, ℎ(, y))︀ × (, y) + (︀ , y, ℎ(, y))︀ where , ≥ 1 are limited sg-polynomial expressions.
Computation through both ℓ-ODE*2 and ℓ-pODE is shown in FTC0 and suficient to capture this class: FTC0 = [0, 1, ℓ, sg, +, − , ÷ 2, ; ∘ , ℓ-ODE*2, ℓ-ODE3]
= [0, 1, ℓ, sg, BIT, +, − , ÷ 2, #, ; ∘ , ℓ-pODE].
In the context of a broader understanding of the hierarchy of small circuit classes, in [12], we also considered non-strict ℓ-ODE schemas. As mentioned, it is shown that IVP defined by linear equations in which ∈ {− 1, 1} and = 0 or such that (, y) occurs only under the scope of the sign function in expressions of the form = sg( (, y) − ) for ∈ N (or = 0, for simple calls) are particularly relevant. As long as (, y) occurs in = − 1 only in expressions of the form sg( (, y) − ), the corresponding computation is in FAC0. Indeed, the solution of such system corresponds to (sharply) bounded search. Here, we additionally consider the following more general, non-strict schema: Definition 5 (Schema ℓ-sODE). Given : N → N and : N+1 → {0, 1}, the function : N+1 → N is defined by ℓ-sODE if it is the solution of the IVP with initial value (0, y) = (y) and such that
= (, y) + (y, (, y)) × (, y) where ∈ {0, 1} is a limited sg-polynomial expression such that calls to (, y) are simple. Computation through this schema is in FAC0 and strong enough to rewrite ℓ-ODE1. Lemma 1. If (, y) is defined by ℓ-sODE from functions in FAC0, then (, y) is in FAC0 as well. Proof. For any ∈ {0, 1}, we use (y) as a shorthand for (, y), where substitutes sg( (, y)). The expression (y) is computable in FAC0 by hypothesis. We consider the main cases: • 0(y) = 1(y). If 1(y) = 0, then for any , (, y) = (y), which can be computed in FAC0 by hypothesis. If 1(y) = 1, then ℓ-sODE is nothing but ℓ-ODE1, the computation of which is shown in FAC0 in [10]. • 0(y) ̸= 1(y). If (y) ≥ 1, then for any , sg( (, y)) = 1, so ( (, y), y) = 1(y), and the proof is precisely as before, i.e. if 1(y) = 0, (, y) = (y); otherwise, this is just an instance of ℓ-sODE. If (y) = 0, then there are two possible sub-cases: (i) if 0(y) = 0, then (, y) = 0; (ii) if 0(y) = 1 (and 1(y) = 0), then if (0, y) = 1, (, y) = 2ℓ(y)− 1 and if (0, y) = 0, (, y) = 0. Both solutions are computable in FAC0.
The schema ℓ-sODE provides the first characterisation of FAC0 based on a non-strict schema, thus ofering a way to compare the defining schema of this class with those defining classes from the levels FNC1 and FAC1 and below (recall that these classes have not characterised by strict schemas). Remark 2. If ( (, y), y) = 1, then ℓ-sODE is equal to ℓ-ODE1.
Proposition 1. FAC0 = [0, 1, ℓ, sg, +, − , ÷ 2, #, ; ∘ , ℓ-sODE, ℓ-ODE3] Proof. (⊇ ) Analogous to [10, Th. 8], plus Lemma 1. (⊆ ) By Remark and [10, Th. 8].
In [12], two non-strict schema, obtained deriving along ℓ and restricting linearity so that = − 1 (in
both cases) and is either in {0, 1} or non-negative, are introduced to capture the class of functions
computed by constant-depth unbounded fan-in circuits including modulo 2 counting gates (FACC[
Definition 6 (Schemas ℓ-b0ODE and ℓ-bODE). Given : N → N and ℎ : N+1 → N, the function : N+1 → N is defined by ℓ-bODE if it is the solution of the IVP with initial value (0, y) = (y) and such that (, y)
= − (, y) + (︀ , y, ℎ(, y), (, y))︀ ℓ where, for any and y, (, y, ℎ(, y), (, y)) ≥ 0 is a sg-polynomial expression, and (, y) occurs in it only in expressions of the form sg( (, y) − ), being constant. In the special case of = ∈ {0, 1} and being a limited sg-polynomial expression such that (, y) occurs in it only under the scope of the sign function, this schema is called ℓ-b0ODE.
It is shown that each of them is suficient to characterize the corresponding class, namely:
FACC[
FNC1 = [0, 1, ℓ, sg, BIT, +, − , ÷ 2, #, ; ∘ , ℓ-pODE, ℓ-bODE].
Additionally, computation through the non-strict and simple schema such that if : N → N and ℎ : N+1 → N, then : N+1 → N defined by the IVP with initial value (0, y) = (y) and such that: where ∈ {0, 1} is a sg-polynomial expression, and (, y) appears in it only in expressions of the form sg( (, y)), is in FNC1. Remarkably, when = 1 and (, y) occurs under the scope of the function BIT only, this schema not only is in FNC1, but it also provides an alternative characterisation of this class. In this case completeness can be proven towards a direct encoding of the corresponding machine model. On the other hand, when = 0 and = ∈ {0, 1} or = ∈ {0, 1} and = 0, i.e. when dealing with IVP with initial value (0, y) = (y) and such that
= (, y, ℎ(, y), (, y)) × (, y)
the corresponding computation is not only in FNC1, but also in FTC0.
In this paper, we presented the global picture of the main results obtained so far to characterise small
circuit computation via discrete ODEs and integrate them with a few new achievements, providing a
uniform and novel approach for studying circuit complexity and provide original strategies (e.g., coming
from the calculus of finite diferences) to tackle notoriously hard open problems in this field, such
as separation results. This would serve as a starting point for future research. Indeed, given the
novelty of this study, many directions are open for investigation. Natural ones include ODE-based
characterisations of the FAC and FNC hierarchies, obtained by endowing algebras defining their base
levels with (variously restricted) schemas obtained deriving along slowly growing function. Related to
this is the exploration of the expressive power of schemas obtained by deriving along ℓ2(= ℓ ∘ ℓ), in
which calls to (, y) occur only under the scope of the function BIT. Another work in progress involves
the investigation of (strict) ℓ-ODEs that correspond to constant-depth classes with modulo counting
gates, which lie between FACC[
Since 2023, the research of Melissa Antonelli has been funded by the Helsinki Institute for Information Technology. The research of Arnaud Durand is partially funded by ANR Grant iference. Melissa Antonelli and Arnaud Durand thank Maupertuis’ SMR Programme, on behalf of the Institute Français in Helsinki, the French Embassy to Finland, the French Ministry of Higher Education, Research and Innovation in partnership with the Finnish Society for Science and Letters and the Finnish Academy of Sciences and Letters, for the financial support. Melissa Antonelli, Arnaud Durand and Juha Kontinen thank Magnus Ehrnrooth for supporting the CARACAL project.
During the preparation of this work, the authors used curre.helsinki.fi in order to: grammar and spelling check. After using these tool, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content. [4] E. Allender, K. W. Wagner, Counting hierarchies: Polynomial time and constant, Bulletin of the
EATCS 40 (1990) 182–194. [5] W. Maass, G. Schnitger, E. D. Sontag, On the computational power of sigmoid versus boolean threshold circuits, in: Proc. FOCS, 1991, pp. 767–776. [6] W. Maass, Bounds for the computational power and learning complexity of analog neural nets,
SIAM J. Comput. 26 (1997) 708–732. [7] T. Barlag, V. Holzapfel, L. Strieker, J. Virtema, H. Vollmer, Graph neural networks and arithmetic circuits, in: Proc. NeurIPS, 2024. [8] I. Parberry, Circuit Complexity and Neural Networks, The MIT Press, 1994. [9] O. Bournez, A. Durand, Recursion schemes, discrete diferential equations and characterization of polynomial time computation, in: Proc. MFCS, 2019. [10] M. Antonelli, A. Durand, J. Kontinen, A new characterization of FAC0 via discrete ordinary diferential equations, in: Proc. MFCS, 2024, pp. 10:1–10:18. [11] M. Antonelli, A. Durand, J. Kontinen, Towards new characterizations of small circuit classes via discrete ordinary diferential equations (short paper), in: Proc. ICTCS, 2024, pp. 166–172. [12] M. Antonelli, A. Durand, J. Kontinen, Characterizing small circuit classes from FAC0 to FAC1 via discrete ordinary diferential equations, in: Proc. MFCS, 2025. [13] A. Cobham, The intrinsic computational dificulty of functions, in: Logic, Methodology and
Phylosophy of Science: Proc. 1964 International Congress, 1965, pp. 24–30. [14] S. Bellantoni, S. Cook, A new recursion-theoretic characetrization of poly-time functions, Comput.
Complex. 2 (1992) 97–110. [15] D. Leivant, Predicative recurrence and computational complexity i: Word recurrence and poly-time, in: Feasible Mathematics, 1994, pp. 320–343. [16] D. Leivant, J.-Y. Marion, Ramified recurrence and computational complexity ii: Substitution and poly-space, in: Proc. CSL, 1995, pp. 369–380. [17] O. Bournez, A. Durand, A characterization of functions over the integers computable in polynomial time using discrete diferential equations, Comput. Complex. 32 (2023). [18] M. Blanc, O. Bournez, A characterization of functions computable in polynomial time and space over the reals with discrete ordinary diferential equations: simulation of Turing Machines with analytic discrete ODEs, in: Proc. MFCS, 2023, pp. 21:1–21:15. [19] M. Blanc, O. Bournez, The complexity of computing in continuous time: Space complexity is precision, in: Proc. ICALP, 2024, pp. 129:1–129:22.