{"id":"57e666d3-7c39-4b51-96ee-ccaf5212b499","arxiv_id":"2506.23404","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Restricted linear discrete ODE schemas characterize the circuit classes FAC^0, FACC[2], FTC^0, FNC1, and FAC^1, with the FACC[2] and FNC1 characterizations being new.","lead":"This paper gives new characterizations of small circuit complexity classes, including FACC[2] and FNC1, using restricted forms of discrete ordinary differential equations. It shows that varying how linear the equation is and the function used for derivation yields exactly the functions computable by circuits of constant or logarithmic depth.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The FNC1 completeness proof in Theorem 4 is unsupported: the proposed ℓ-bODE encoding of 4-BRN collapses all inputs of the same length to one value, while 4-BRN can distinguish them. A concrete 4-BRN instance with f(2)=0 and f(3)=1 cannot be the solution of any ℓ-bODE.","rationale":"The reader's weakest assumption was the sketchiness of the Clote-algebra encodings. My concern is sharper: the 4-BRN encoding as displayed is not merely under-detailed, it is inconsistent with the semantics of ℓ-ODE. The equality on length blocks is a direct consequence of Definition 1 and is easy to verify; the counterexample is a legitimate 4-BRN function. If the test is run and confirms the mismatch, Theorem 4 cannot stand as proved. I still credit the framework and the upper-bound lemmas, but the FNC1 completeness claim is load-bearing for the abstract's main novelty. The same block-constancy issue also threatens the 1-BRN route to FACC[2], although the primary concern is already from Theorem 4. I therefore move the verdict from CONDITIONAL to REJECT for this version, with the caveat that a corrected encoding would change the assessment.","tokens_in":29943,"tokens_out":18810,"duration_ms":198981,"concrete_test":"Instantiate the Theorem 4 encoding on the N'_0-definable 4-BRN instance f(0)=0, f(s_0(x))=0, f(s_1(x))=1. Write the ℓ-bODE IVP exactly as in the proof and evaluate it with Definition 10 at x=2 and x=3. The recurrence is frozen inside the block, so the two values coincide, while the 4-BRN values are 0 and 1. This settles whether the displayed encoding is correct; a successful repair must either show a different ℓ-bODE for this instance or explain how the scheme distinguishes 2 from 3 without violating the block-constancy of ℓ-ODE.","verdict_should_be":"REJECT","load_bearing_attack":"Definition 1 (and hence every ℓ-bODE instance) forces f(x+1,y)=f(x,y) whenever ℓ(x+1)=ℓ(x), so any ℓ-ODE solution is constant on each length block {2^{n-1},...,2^n-1}. Theorem 4's completeness argument claims to encode Clote's 4-BRN by the displayed IVP whose right-hand side is built from h_{z(x)}(ℓ(x),y,i) and indicators of the current value. Read through Definition 10, the update is evaluated at α(ℓ(x)-1), the last number of the previous length block; the value of z(x) there is the same for all x of the current length. The equation therefore defines a single chain indexed by length, not the binary prefix recursion of 4-BRN. This is not a mere gap: take the 4-BRN instance g(0)=0, h_0(x,y,v)=0, h_1(x,y,v)=1, which is certainly in N'_0. It gives f(2)=0 and f(3)=1. No ℓ-bODE solution can have these two values, since 2 and 3 lie in the same length block. The displayed encoding in Theorem 4 therefore fails for this instance, and the same length-block obstruction applies to the 1-BRN encoding used in the alternative proof of Theorem 2. Since FNC1 completeness is a headline contribution, the paper as written lacks a valid proof of Theorem 4.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":30235,"tokens_out":10990,"duration_ms":121952,"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":[{"comment":"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.","section":"§4.4, Theorem 4"},{"comment":"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.","section":"§4.4, Lemma 5"},{"comment":"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.","section":"Appendix A.5, Theorem 2"},{"comment":"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.","section":"§5, Lemma 9"}],"minor_comments":[{"comment":"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.","section":"§4.2, Lemma 2 proof"},{"comment":"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.","section":"§4.4, Theorem 4"},{"comment":"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.","section":"§4.4, Lemma 4 proof sketch"},{"comment":"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.","section":"§5, Lemma 9 proof"},{"comment":"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.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The paper has a clear and attractive framework, and several upper-bound lemmas appear to be correct and useful. However, the two headline completeness theorems (Theorems 2 and 4) are not proven as written, and the appendix does not repair the defects. The length-block obstruction is a concrete, load-bearing problem: the proposed encodings of 4-BRN and 1-BRN cannot work. A major revision would need a fundamentally different completeness construction (for example, a table-based encoding over length blocks) or a careful weakening of the claims. If such a construction is found, the paper could be a valuable contribution; in its present form, the central claims are not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a useful framework paper, but the headline FNC1 result is not proved. I agree with the stress-test note: the 4-BRN encoding in Theorem 4 is incompatible with Definition 1. For any ℓ-ODE, f(x+1)=f(x) whenever ℓ(x+1)=ℓ(x), so every solution is constant on each length block. The 4-BRN instance g(0)=0, h0=0, h1=1 gives f(2)=0 and f(3)=1; no ℓ-bODE solution can do that. The same length-block problem affects the 1-BRN encoding in the alternative proof of Theorem 2. This is a load-bearing gap, not a cosmetic one.\n\nWhat is genuinely new and good: the paper gives a single schema picture spanning FAC0, FACC[2], FTC0, FNC1, and FAC1, and the ℓ2-ODE result (Lemma 9) is a real addition. The membership direction for ℓ-b0ODE in FACC[2] is plausible, and the parity example is natural. The paper is honest that most proofs are only sketched, and the appendix does contain real work. The FAC0/FTC0 portions are extensions of the authors' own prior framework rather than a paradigm shift, but they are cleaner and more uniform.\n\nSoft spots beyond Theorem 4: Lemma 5 assumes ℓ(x) is a power of two \"to avoid rounding\" and does not remove that assumption; several display equations have missing parentheses or undefined notation; and the paper leans on Clote's algebras as black boxes. Those are fixable. The FNC1 completeness direction is not.\n\nWho this is for: people working in implicit complexity and function-algebra characterizations of small circuit classes. The framework is worth engaging with, and the FACC[2] and FTC0 parts may well be right, but the paper cannot be accepted in its current form while the FNC1 characterization rests on an encoding that contradicts the defining schema.","headline":"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.","tokens_in":30808,"tokens_out":3885,"would_cite":false,"duration_ms":40353,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D15","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Discrete ordinary differential equations characterize the circuit classes FACC[2] and FNC1, giving the first ODE-based descriptions of both function classes.","keywords":["discrete ordinary differential equations","small circuit classes","FACC[2]","FNC1","function algebras","length-ODE","implicit computational complexity","recursion schemas"],"falsifier":"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.","tokens_in":29711,"feed_emoji":"🧮","tokens_out":4310,"duration_ms":42567,"temperature":0.7,"pith_summary":"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.","feed_headline":"ODE recursions capture two circuit classes","feed_subtitle":"Length-based difference equations characterize FACC[2] and FNC1, giving a uniform view from AC0 to AC1.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the ODE/linear-length recursion method this paper extends, including derivation along ℓ and linearity as growth control.","marker":"[9]"},{"why":"Established the earlier FAC^0 and FTC0 ODE characterizations that this paper improves and generalizes.","marker":"[2]"},{"why":"Gives Clote's algebra A0 = FAC^0 via CRN, used as the target of the ℓ-ODE1 and ℓ-ODE3 encoding.","marker":"[12]"},{"why":"Provides Clote's k-BRN characterization of FNC1, specifically 4-BRN, which the completeness proof for FNC1 encodes as ℓ-bODE.","marker":"[13]"},{"why":"Supplies Clote–Takeuti's 1-BRN and CRN characterization of FACC[2], used in the alternative completeness proof.","marker":"[16]"},{"why":"Proves parity is not in AC0, justifying the claim that ℓ-b0ODE genuinely exceeds FAC^0.","marker":"[22]"},{"why":"Shows iterated multiplication is in FTC0, used for the closure proof of ℓ-pODE.","marker":"[24]"},{"why":"Provides standard facts about circuit classes and iterated addition used in the FTC0 and FAC^1 membership arguments.","marker":"[33]"}],"fun_headline_variants":["First ODE characterizations for FACC[2] and FNC1","Length-based ODEs exactly capture FACC[2] and FNC1","ODE algebra exactly equals FACC[2] and FNC1","Uniform ODE framework spans FAC^0 to FAC^1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["First ODE characterizations for FACC[2] and FNC1","Length-based ODEs exactly capture FACC[2] and FNC1","ODE algebra exactly equals FACC[2] and FNC1","Uniform ODE framework spans FAC^0 to FAC^1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00159,"raw_usage":{"total_tokens":6357,"prompt_tokens":984,"completion_tokens":5373,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":5294}},"tokens_in":600,"tokens_out":5373,"duration_ms":37048,"temperature":1.0,"reasoning_tokens":5294,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:43:06.272348+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bournez and A","cited_arxiv_id":null,"evidence_quote":"Supplies the ODE/linear-length recursion method this paper extends, including derivation along ℓ and linearity as growth control."},{"cited_title":"Antonelli, A","cited_arxiv_id":null,"evidence_quote":"Established the earlier FAC^0 and FTC0 ODE characterizations that this paper improves and generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives Clote's algebra A0 = FAC^0 via CRN, used as the target of the ℓ-ODE1 and ℓ-ODE3 encoding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Clote's k-BRN characterization of FNC1, specifically 4-BRN, which the completeness proof for FNC1 encodes as ℓ-bODE."},{"cited_title":"Clote and G","cited_arxiv_id":null,"evidence_quote":"Supplies Clote–Takeuti's 1-BRN and CRN characterization of FACC[2], used in the alternative completeness proof."},{"cited_title":"Furst, J.B","cited_arxiv_id":null,"evidence_quote":"Proves parity is not in AC0, justifying the claim that ℓ-b0ODE genuinely exceeds FAC^0."},{"cited_title":"Hesse, E","cited_arxiv_id":null,"evidence_quote":"Shows iterated multiplication is in FTC0, used for the closure proof of ℓ-pODE."},{"cited_title":"iterated multiplication","cited_arxiv_id":null,"evidence_quote":"Provides standard facts about circuit classes and iterated addition used in the FTC0 and FAC^1 membership arguments."}],"review_version":1}