Pith. sign in

REVIEW 4 major objections 5 minor 33 references

Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Discrete ordinary differential equations characterize the circuit classes FACC[2] and FNC1, giving the first ODE-based descriptions of both function classes.

desk verdict The paper builds a promising uniform ODE framework for small circuit classes, but the FNC1 completeness claim is unsupported: the proposed ℓ-bODE encoding of 4-BRN is incompatible with Definition 1. read the letter →

arxiv 2506.23404 v1 pith:TXC4C6Y6 submitted 2025-06-29 cs.CC cs.LO

Melissa Antonelli , Arnaud Durand , Juha Kontinen This is my paper · ORCID
classification cs.CCcs.LO MSC 03D1568Q15
keywords discreteordinarydifferentialequationssmallcircuitclassesFACC[2]FNC1functionalgebraslength-ODEimplicitcomputationalcomplexityrecursionschemas
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that discrete ordinary differential equations—difference equations whose derivative is taken along a slowly growing clock function—form a single, uniform lens for the small circuit classes between $FAC^{0}$ and $FAC^{1}$. The authors show that by tuning two knobs, whether the equation may refer to the function being defined and how fast the derivation clock grows, the same linear ODE schema computes exactly the functions in $FAC^{0}$, FACC[2], FTC0, FNC1, and $FAC^{1}$. The headline results are the first ODE-based characterizations of FACC[2] (constant-depth unbounded fan-in circuits with Mod 2 gates) and FNC1 (logarithmic-depth bounded fan-in circuits). If the characterizations hold, these circuit classes share a common recursion-theoretic description, and questions about circuit depth become questions about allowed feedback and clock speed in a difference equation.

What carries the argument

The engine is the discrete length-ODE schema, ∂f(x,y)/∂ℓ = h(x,y,f(x,y)), which is shorthand for f(x+1,y)=f(x,y)+(ℓ(x+1)−ℓ(x))·h(x,y,f(x,y)). Deriving along ℓ means the value changes only when ℓ does, roughly once per binary-length block, so the number of effective recursion steps is ℓ(x), not x. Linearity—requiring the right-hand side to be essentially linear in f and restricting which arguments may call f (none, only under the sign function, or under threshold sign tests)—controls the size of intermediate values. The sign function sg and the encoding of the bit function BIT via the half-shift ℓ-ODE3 schema let the algebra read and write bits of a binary string, which is how the encodings of Clote's CRN and k-BRN recursions are carried out.

What would settle it

Find a function definable by Clote's 4-BRN schema whose ℓ-bODE encoding as written in Theorem 4 provably requires super-logarithmic depth or exponential size when implemented with bounded fan-in circuits; equivalently, exhibit an instance where the rounding assumption in Lemma 5 changes the value of the encoded 4-BRN function, breaking the claimed FNC1 membership.

Watch

Extended reading notes

Core claim

The central discovery is that the linear length-ODE schema, written as f(x+1,y)=f(x,y)+(ℓ(x+1)−ℓ(x))·(A(x,y,h,f)·f(x,y)+B(x,y,h,f)) and abbreviating the derivative along ℓ, stratifies the small circuit classes according to which calls to the defined function f are allowed and how the coefficient functions are constrained. When no calls to f are allowed, the schema captures FTC0; when coefficients and the added term are restricted to {0,1}, with A=−1 and B depending on f only through sign tests, it captures FACC[2]; allowing B to be any nonnegative expression with f only under sign tests captures FNC1. The paper proves that the algebra built from basic arithmetic, composition, ℓ-ODE1, ℓ-ODE3, and ℓ-b0ODE equals exactly FACC[2], that the algebra built from ℓ-pODE and ℓ-bODE equals exactly FNC1, and that the full linear ℓ2-ODE schema, deriving along ℓ∘ℓ, is computable in FNC1.

Load-bearing premise

The completeness results hinge on the claim that Clote's recursion schemas (CRN, 1-BRN, 4-BRN) can be faithfully rewritten as instances of the paper's ℓ-ODE schemas; the 4-BRN to ℓ-bODE encoding is only sketched, and the proof of Lemma 5 assumes ℓ(x) is a power of two to avoid rounding.

Editorial extensions

If this is right

  • The algebra ACDL extended by ℓ-b0ODE characterizes exactly FACC[2], so parity and related Mod-2 counting become natural ℓ-b0ODE instances.
  • The algebra built on ℓ-pODE and ℓ-bODE characterizes exactly FNC1, and in particular Clote's 4-BRN schema, a generator of FNC1, is encoded as an ℓ-bODE with threshold tests on the current value.
  • Deriving along ℓ2 instead of ℓ changes the picture: strict ℓ2-ODE equations give FAC^0 (log-iterated sums), non-strict ones give FTC0, and the full linear ℓ2-ODE schema is computable in FNC1.
  • Since FAC^0 is properly contained in FACC[2] and the new schemas form one hierarchy of linearity constraints, the ODE framework offers a uniform view of circuit hierarchies from AC0 to AC1.
  • The ℓ2-ODE result suggests a general principle: a slower derivation clock corresponds to a weaker circuit class, mirroring the role ℓ plays for polynomial time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If these characterizations are correct, one could try to separate further circuit classes by proving that no ℓ-ODE with a given syntactic restriction can compute a specific function, turning circuit lower bounds into lower bounds on ODE schemas.
  • The ℓ2-ODE result hints that replacing ℓ by iterated logarithms might yield characterizations of deeper subclasses, though the paper does not claim this.
  • A natural testable extension is to add Mod p gates for odd primes: the paper leaves open whether a schema between ℓ-b0ODE and ℓ-pODE corresponds to FACC[p].
  • The explicit assumption in Lemma 5 that ℓ(x) is a power of two suggests that a fully rounding-free encoding would be needed to make the FNC1 completeness proof entirely constructive.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper develops a uniform ODE-based framework for small circuit classes. It introduces several discrete ordinary differential equation schemas obtained by deriving along the length function ℓ or along the slower function ℓ2, with varying restrictions on linearity and on the occurrence of the function being defined. The main positive results are upper-bound lemmas showing that solutions of these schemas are computable in specific circuit classes, and completeness theorems claiming the first ODE-based characterizations of FACC[2] (Theorem 2, via the schema ℓ-b0ODE added to the algebra ACDL) and of FNC1 (Theorem 4, via the algebra generated by ℓ-pODE and ℓ-bODE). The paper also proves that a linear ℓ2-ODE schema is computable in FNC1 (Lemma 9) and offers a unified picture in Figure 1. Most proofs are presented as sketches, with an appendix intended to supply details.

Significance. If the main theorems were correct, the paper would provide the first ODE-based characterizations of FACC[2] and FNC1, extending the authors' earlier FAC^0 characterization and giving a uniform framework for circuit classes via constraints on linearity and derivation length. The examples (parity, bounded search, bit extraction, iterated sum/product) are natural and suggestive, and the upper-bound lemmas appear plausible and useful. The paper also benefits from testing its new schemas against independent algebras due to Clote and Clote-Takeuti, which is a good methodological choice. However, the two headline completeness theorems are not established by the arguments as written: the central encoding of 4-BRN in Theorem 4 is contradicted by a simple length-block obstruction, and the alternative completeness proof for Theorem 2 suffers from the same defect. The significance of the paper therefore remains conditional on a substantially repaired completeness argument.

major comments (4)
  1. [§4.4, Theorem 4] The completeness direction of Theorem 4 is invalid as written. By Definition 1, any solution of an ℓ-ODE satisfies f(x+1,y)=f(x,y) whenever ℓ(x+1)=ℓ(x); hence every ℓ-bODE solution is constant on each length block {2^{n-1},...,2^n-1}. In the displayed encoding of 4-BRN in Theorem 4, the right-hand side is evaluated at α(ℓ(x)-1), and z(x)=BIT(ℓ(y)-ℓ(x)-1,y) depends on x only through ℓ(x); therefore the proposed 4brn(x,y) is constant on each block. But 4-BRN is not block-constant: take g(0)=0, h_0(x,y,v)=0, and h_1(x,y,v)=1; then a valid 4-BRN instance gives f(2)=0 and f(3)=1, yet 2 and 3 belong to the same length block. This is a concrete counterexample to the proposed encoding, so the proof does not establish that every FNC1 function belongs to the algebra. The appendix repeats the same encoding and does not address this issue.
  2. [§4.4, Lemma 5] The proof of Lemma 5 begins with 'w.l.o.g. let us suppose that ... ℓ(x) is a power of two (to avoid rounding)'. This is not a harmless normalization: ℓ(x) takes all positive integer values, and FNC1 is a class of functions on all inputs. The divide-and-conquer construction splits at ℓ(x)/2, and for arbitrary x the two halves have unequal lengths; the subsequent selection and concatenation steps depend on the rounding. The proof as written covers only lengths that are powers of two. Since Lemma 5 is used for the upper-bound direction of Theorem 4, this is a second gap in the FNC1 argument.
  3. [Appendix A.5, Theorem 2] The alternative completeness proof for Theorem 2 via 1-BRN has the same length-block defect. The displayed IVP has right-hand side depending on h(ℓ(x), y, i), which is constant on each block {2^{n-1},...,2^n-1}, while 1-BRN may assign different values to x=2 and x=3. The main proof of Theorem 2 in §4.2 only states that the inclusion follows from '[2, Th.18]' and the simulation of parity, without supplying a complete derivation. Thus, as written, Theorem 2 also lacks a valid completeness proof: the 1-BRN encoding fails, and the cited consequence is not spelled out.
  4. [§5, Lemma 9] The proof of Lemma 9 contains an incorrect complexity count: it says 'There are O(ℓ2(x)) such choices' for pairs (a,b) ∈ {0,1}^{2ℓ2(x)}, but there are actually 2^{2ℓ2(x)} = O(ℓ(x)^2) choices. More importantly, the global consistency check and the final selection step are described only verbally, without explicit circuit size and depth bounds. Since Lemma 9 states that ℓ2-ODE is computable in FNC1, the proof needs to be completed with a precise construction and complexity analysis.
minor comments (5)
  1. [§4.2, Lemma 2 proof] The displayed formula in the proof of Lemma 2 contains malformed expressions such as '(K0(x) = K1(x) − 1)' and later '(K0(x) = K1(x) − 1)' where a negation or inequality symbol appears to be missing; please correct the parenthesization and the Boolean notation.
  2. [§4.4, Theorem 4] The display uses the notation '4brn(x, y, y)' for the initial value and later '4brn(x, x, z)' for the final equality; the arity of the function is inconsistent, and the role of each argument should be defined explicitly.
  3. [§4.4, Lemma 4 proof sketch] In the proof sketch of Lemma 4, the symbol s(ℓ(x)/2 − 1) is used before the notation s is introduced; please define s(x) explicitly at the start of the proof.
  4. [§5, Lemma 9 proof] The phrase 'log 3(x)' in the proof of Lemma 9 is presumably a typo for O(log^3 x) or a similar asymptotic expression; please correct it.
  5. [Figure 1] The caption refers to 'Schemas in blue', but the figure is not rendered in color in the manuscript; please indicate the distinction between characterized and merely upper-bounded schemas in a way that does not rely on color.

Circularity Check

1 steps flagged · score 6.0 of 10

FACC[2] completeness contains a self-referential IVP in the appendix; the central FNC1/FAC0 arguments rely on external or prior algebras rather than on their own claims.

  1. self definitional [Appendix A.5, ODE-Based Characterizations of FACC[2], Alternative Proof of Theorem 2]
    "It remains to show that a function f (x, y) defined by 1-BRN from g and h as follows: f (0, y) = g(y), f (x, y) = h(x, y, f(ℓ(x), y)) with f (x, y) ≤ 1, can be rewritten as the solution of the IVP below: 1brn(0, y) = g(y), ∂1brn(x, y)/∂ℓ = −1brn(x, y) + sg(f (x, y)) × h(ℓ(x), y, 1) + cosg(f (x, y)) × h(ℓ(x), y, 0), which is an instance of (limited) ℓ-b0ODE."

    The IVP is claimed to define the new function 1brn from g and h alone, but its right-hand side contains sg(f(x,y)) and cosg(f(x,y)), where f is exactly the 1-BRN function whose definability in the algebra is being proved. Thus the 'solution' of the IVP is not an independent construction from the given data; the target function f is supplied as an oracle inside the defining equation. The claimed reduction therefore assumes the conclusion: the simulation of 1-BRN by ℓ-b0ODE is asserted by writing f into the IVP rather than derived. Even setting aside the additional mismatch that h is evaluated at ℓ(x) instead of x, this is a self-definitional step in the completeness proof of the FACC[2] characterization.

full rationale

The paper's soundness directions are mostly self-contained: Lemmas 2, 5 and 9 give circuit upper bounds for the ODE schemas and do not presuppose the target algebra. The completeness arguments, however, pass through Clote's algebras (A0, N'0, 1-BRN/4-BRN) and the authors' prior result [2] ACDL = FAC0; those are external or separately published results, so citing them is not by itself circular. The one genuine circular step is localized in the appendix's alternative proof of Theorem 2: the IVP intended to encode 1-BRN calls the target function f inside sg/cosg, so the claimed encoding is circular by construction. The skeptic's length-block objection to Theorem 4—any ℓ-bODE solution is constant on each block {2^{n-1},...,2^n-1}, while 4-BRN can distinguish x with the same length—is a failure of the displayed encoding, not a reduction of a prediction to its inputs; under the hard rules it is a correctness risk rather than a circularity. Because one supporting completeness proof reduces to its own target, but the central claims still have independent content elsewhere, the score is 6 rather than 8 or 10.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on known algebra characterizations from Clote and Clote-Takeuti, on the prior ODE framework of [9,10], and on new encodings that are mostly sketched. There are no fitted parameters and no invented physical or mathematical entities beyond the schemas themselves.

assumptions (5)
  • domain assumption Clote's algebra A0 characterizes FAC^0 (A0 = FAC^0).
    Used as a black box in Theorem 1's completeness proof; cited from [12].
  • domain assumption Clote's algebra N'0 with 4-BRN characterizes FNC1.
    Used in Theorem 4's completeness proof; cited from [13].
  • domain assumption Clote and Takeuti's algebra with 1-BRN characterizes FACC[2].
    Used in Theorem 2's completeness proof; cited from [16].
  • standard math Dlogtime-uniform circuit families are closed under the composition and substitution operations used in the proofs.
    Assumed throughout; standard in circuit complexity, but not proved here.
  • standard math The discrete derivative definition and the solution formula for linear ℓ-ODEs from [9,10] are sound.
    Relying on prior published definitions and results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations." pith.science (2026). https://pith.science/paper/TXC4C6Y6

@misc{pith2026250623404,
  author       = {Pith},
  title        = {Pith review of: Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TXC4C6Y6}},
  note         = {Machine review of arXiv:2506.23404}
}
read the original 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 (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 FAC^0 to 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 (FACC[2]) and in logarithmic depth with bounded fan-in Boolean gates (FNC1).

Figures

Figures reproduced from arXiv: 2506.23404 by the authors.

Figure 1
Figure 1. ODE Schemas and Small Circuit Classes in a Nutshell [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 30 canonical work pages

  1. [2]

    Antonelli, A

    M. Antonelli, A. Durand, and J. Kontinen. A new characterization of F AC0 via discrete ordinary differential equations. In Proc. MFCS, 2024

    work page 2024

  2. [1]

    B. Allen. Arithmetizing uniform NC. Ann. Pure Appl. Logic , 53:1–50, 1991

    work page 1991

  3. [3]

    T. Arai. A bounded arithmetic AID for Frege systems. Ann. Pure Appl. Logic , 103:155–199, 2000

    work page 2000

  4. [4]

    Barrington, N

    D.A.M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC 1. J. of Comput. and Syst. Sc. , 41:274–306, 1990

    work page 1990

  5. [5]

    Bellantoni and S

    S. Bellantoni and S. Cook. A new recursion-theoretic characterization of poly-time functions. Comput. Complex. , 2:97–110, 1992

    work page 1992

  6. [6]

    Blanc and O

    M. Blanc and O. Bournez. A characterisation of functions computable in polynomial time and space over the reals with discrete ordinary differential equations: simulation of Turing Machines with analytic discrete ODEs. In Proc. MFCS, pages 21:1–21:15, 2023

    work page 2023

  7. [7]

    Blanc and O

    M. Blanc and O. Bournez. The complexity of computing in continuous time: Space complexity is precision. In Proc. ICALP, pages 129:1–129:22, 2024

    work page 2024

  8. [8]

    Bonfante, R

    G. Bonfante, R. Kahle, J.-Y. Marion, and I. Oitavem. Two function algebras defining functions in NC k boolean circuits. Inf. and Comput. , 2016

    work page 2016

Show all 33 references
  1. [9]

    Bournez and A

    O. Bournez and A. Durand. Recursion schemes, discrete differential equations and characterization of polynomial time computation. In Proc. MFCS, 2019

    2019

  2. [10]

    Bournez and A

    O. Bournez and A. Durand. A characterization of functions over the integers com- putable in polynomial time using discrete differential equations. Comput. Complex. , 32(7), 2023

    2023

  3. [11]

    P.G. Clote. A sequential characterization of the parallel complexity class NC. Technical report, Boston College, 1988

    1988

  4. [12]

    P.G. Clote. Sequential, machine-independent characterizations of the parallel complex- ity classes AlogTIME, ACk, NCk and NC, pages 49–69. Progress in Computer Science and Applied Logic. Birkh¨ auser, Boston, MA, 1990

    1990

  5. [13]

    P.G. Clote. On polynomial size Frege proofs of certain combinatorial principles. In P. Clote and Krj ´ ıcek J., editors,Arithmetic, Proof Theory, and Computational Com- plexity, pages 166–184. Clarendon Press, 1993. 21

    1993

  6. [14]

    Clote and E

    P.G. Clote and E. Kranakis. Boolean Functions and Computation Models . Springer, 1998

    1998

  7. [15]

    Clote and G

    P.G. Clote and G. Takeuti. Bounded arithmetic for NC, ALogTIME, L and NL. Ann. Pure and Appl. Logic , 56:73–117, 1992

    1992

  8. [16]

    Clote and G

    P.G. Clote and G. Takeuti. First order bounded arithmetic and small complexity classes. In P.G. Clote and J.B. Remmel, editors, Feasible Mathematics II, pages 154–

  9. [17]

    A. Cobham. The intrinsic computational difficulty of functions. In Logic, Methodology and Phylosophy of Science: Proc. 1964 International Congress , pages 24–30. 1965

    1964

  10. [18]

    Compton and C

    K.J. Compton and C. Laflamme. An algebra and a logic for NC 1. Inf. Comput. , 87(1/2):240–262, 1990

    1990

  11. [19]

    Cook and T

    S. Cook and T. Morioka. Quantified propositional calculus and a second-order theory for NC1. Arch. Math. Logic, 44:711–749, 2005

    2005

  12. [20]

    Cook and P

    S. Cook and P. Nguyen. Theories for TC 0 and other small circuit classes. Log. Meth. Comput. Sci. , 2(1–40), 2006

    2006

  13. [21]

    Durand, A

    A. Durand, A. Haak, and H. Vollmer. Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth. In Proc. LICS, pages 354–363, 2018

    2018

  14. [22]

    Furst, J.B

    M.L. Furst, J.B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hier- archy. In Proc. FOCS, pages 260–270, 1981

    1981

  15. [23]

    Gurevich and H

    Y. Gurevich and H. Lewis. A logic for constant-depth circuit. Inf. Control, 61:65–74, 1984

    1984

  16. [24]

    Hesse, E

    W. Hesse, E. Allender, and D.A.M. Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695–716, 2002

    2002

  17. [25]

    Immerman

    N. Immerman. Languages that capture complexity classes. SIAM J. Comput., 16:760– 778, 1987

    1987

  18. [26]

    Johannsen

    J. Johannsen. A bounded arithmetic theory for constant depth threshold circuits , vol- ume 6 of Springer Lecture Notes in Logic, chapter G ¨ODEL ’96, pages 224–234. H´ ajek, P., 1996

    1996

  19. [27]

    D. Leivant. Predicative recurrence and computational complexity I: Word recurrence and poly-time. In Feasible Mathematics. Birkh¨ user, 1994. 22

    1994

  20. [28]

    Leivant and J.-Y

    D. Leivant and J.-Y. Marion. Ramified recurrence and computational complexity II: Substitution and poly-space. In Proc. CSL, pages 369–380, 1995

    1995

  21. [29]

    Leivant and Y.-Y

    D. Leivant and Y.-Y. Marion. Lambda calculus characterizations of poly-time. Fun- dam. Inform. , 19(1,2):167–184, 1993

    1993

  22. [30]

    S. Lindell. A purely logical characterization of circuit uniformity. In 7th Structure in Complexity Theory Conf. , pages 185–192, 1992

    1992

  23. [31]

    Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

    A.A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41:333–338, 1987

    1987

  24. [32]

    Algebraic methods in the theory of lower bounds for boolean circuit complexity

    R Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA , pages 77–82. ACM, 1987. doi:10.1145/28395.28404

    1987

  25. [33]

    iterated multiplication

    H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach . Springer, 1999. 23 A Proofs for Section 4 (Investigating Circuit Complexity Deriving along ℓ) A.1 Strict Schemas in F AC0 Lemma 10. Let k : Np → {0, 1} be computable in F AC0. Then, the function f : Np+1 → N ...

    1999

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.