{"id":"358f90d6-b427-41f0-9eb7-1c512e6ec28f","arxiv_id":"2506.19104","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The author constructively programs deep ReLU networks to sort exactly and to approximate special functions with exponentially small error, using folding operations and conditional branching.","lead":"This paper shows how to build deep ReLU neural networks by hand to exactly sort numbers and to approximate exponentials, trigonometric functions, monomials, and multiplication with exponential accuracy. It presents a way to 'compile' recursive algorithms into neural network weights, making the networks fully understandable instead of trained black boxes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central folding theorem is misindexed: Eq. (10) uses p_j where the pre-fold argument p_{j-1} is required, making Theorem 3.1 false as stated.","rationale":"The reader's verdict is CONDITIONAL, and our stress test reaches the same overall judgment, so the verdict is unchanged. However, the most load-bearing concern is not the Assumption 2/crossing-condition gap highlighted by the reader, but the concrete indexing error in Eq. (10) and Theorem 3.1. That error makes the central approximation theorem false as stated and the accompanying proof invalid; it is not merely a stylistic issue. It does not sink the paper because the Julia implementation and Algorithm 3 conform to the corrected indexing, and the same fix propagates cleanly. The Assumption 2 concern is genuine but less decisive: for the specific examples the crossing constants are given analytically, and the required inequalities appear checkable for every level. Thus the paper should be accepted only after the indexing correction is made in the statement and proof of Theorem 3.1, and after any downstream references to Eq. (10) are adjusted. The exact-sorting construction in §2 appears sound and is supported by explicit weights and the public repository.","tokens_in":18088,"tokens_out":14662,"duration_ms":144670,"concrete_test":"Recompute Eq. (10) for L=1 at x=3/4: the printed formula gives f_1(3/4)=η_1(h_1(3/4))=η_1(1/4)=0, while Algorithm 3 returns 2x−1=1/2, so the identity in Theorem 3.1 fails. Then re-derive the theorem with the corrected sum Σ_{j=1}^L η_j(p_{j-1}(x)); verify that x^2−f_L(x)=p_L(x)^2 now holds for L=1,...,10, and confirm the resulting errors match the Julia package's square_approx output. If the corrected identity is confirmed, the concern is a fixable indexing error rather than a conceptual flaw.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 defines p_j recursively as the value after j folds: p_1(x)=h_1(x), p_2(x)=h_2(p_1(x)), ..., so p_j(x) lies in [0,2^{-j}]. Equation (10) then defines f_L(x)=Σ_{j=1}^L η_j(p_j(x)), and Theorem 3.1 asserts x^2−f_L(x)=p_L(x)^2. This is false as written. The correction η_j in (9) is defined for the pre-fold argument: at level j it must be evaluated at p_{j-1}(x), the value before h_j is applied, not at p_j(x). For L=1, (10) gives f_1(x)=η_1(h_1(x))≡0 on [0,1], because h_1(x)∈[0,1/2] and η_1 is supported only on [1/2,1]. Algorithm 3, and the correct unfolding (8), instead yield η_1(x)=max(0,2x−1). Thus the displayed theorem and the proof identity x^2=p_L(x)^2+Σ_{j=1}^L η_j(p_j(x)) are invalid. The claimed 2^{-2L} approximation rate is therefore not proven by the manuscript as stated; the statement becomes correct only after replacing every p_j in the sum by p_{j-1} (with p_0(x)=x). This is a fixable but load-bearing error: the later exponential, trigonometric, monomial, and multiplication constructions all rely on the same unfolding mechanism, so the paper's formal justification for those rates shares the defect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a constructive, algorithmic view of deep ReLU networks. It first builds an exact sorting network by wiring comparison elements according to the bitonic-sort schedule, with min/max implemented by two ReLU layers. It then introduces a geometric folding/unfolding scheme on graded dyadic meshes to approximate x^2 with error O(2^{-2L}), and proposes a general framework for compiling conditional expressions into ReLU networks under a crossing assumption (Assumption 2). The framework is applied to exponentials, trigonometric functions, monomials, and multiplication, with claimed convergence O(2^{-2L}) and with explicit constants and Julia code supplied.","tokens_in":18405,"tokens_out":11992,"duration_ms":116191,"significance":"If the formal statements are corrected, the paper is a valuable contribution to constructive expressivity results for ReLU networks. Its strengths include the explicit, deterministic bitonic-sort construction with exact sorting; the transparent derivation of all weights; the reproducible Julia package; and the demonstration that conditional branching can be compiled into continuous ReLU networks. The paper also honestly attributes prior results, notably Telgarsky's x^2 construction, and extends it to several new function families. The main value is pedagogical and methodological: it shows concretely what can be programmed into a ReLU network and gives explicit error rates. However, the manuscript as written contains indexing and sign errors in central equations, so the formal justification of the claimed rates is not yet reliable.","major_comments":[{"comment":"The definition of f_L in Eq. (10) is misindexed. With p_j(x) defined as the value after j folds, p_j(x) lies in [0,2^{-j}], so eta_j(p_j(x)) is evaluated on the wrong interval; for L=1 one gets eta_1(h_1(x)) = 0 on [0,1], and Theorem 3.1 is false as stated. The correct unfolding is f_L(x) = sum_{j=1}^L eta_j(p_{j-1}(x)) with p_0(x)=x, and the identity should read x^2 = p_L(x)^2 + sum_{j=1}^L eta_j(p_{j-1}(x)). This is load-bearing because the later exponential, trigonometric, monomial, and multiplication constructions all rely on the same unfolding mechanism, and the formal proof of their O(2^{-2L}) rates inherits the defect. The algorithms themselves appear to implement the correct recurrence; the theorem statement and proof need to be fixed.","section":"Section 3.2, Eq. (10) and Theorem 3.1"},{"comment":"Equation (20) uses b(0) as the additive constant, but the general critical point is x*, not 0. The correct formula should have b(x*) in place of b(0); otherwise, for x > x*, the expression evaluates to b(x) only if b(0)=b(x*), which is not assumed. This is not a cosmetic issue: in the examples in Section 5, b(x*) = e^{s_j} or similar, which is not b(0). The derivation above (20) and the definitions of \\hat b and \\hat c clearly use b(x*), so Eq. (20) appears to contain a typo, but it must be corrected before the compilation formula is usable.","section":"Section 4.3, Eq. (20)"},{"comment":"The sign convention stated for Eq. (17) is incorrect. The formula z(x)=b(0)+ReLU(b(x)-b(0))+ReLU(c(x)-c(0)) implements the conditional only when \\hat b(x) is nonnegative for x >= 0 and \\hat c(x) is nonnegative for x <= 0 (or the symmetric case), not when both functions are 'positive for x >= 0'. As written, the assertion that (17) is equivalent to the if-then-else statement is false. This is a special-case precursor to the general compilation formula, so the error should be fixed by stating the correct sign conditions.","section":"Section 4.2, Eq. (17)"},{"comment":"The paper asserts that the constants beta and gamma stated in Sections 5.1-5.3 satisfy Assumption 2, but it does not give a complete proof for all levels j. The figures and the phrase 'by direct computation' are not a substitute for an inequality argument, especially because a failure of the crossing condition at any level would make the compiled network select the wrong branch on some interval. Please add a short lemma, for example using convexity or monotonicity of the relevant functions, verifying that the stated beta and gamma give the required sign pattern for every j. The constants appear plausible and the numerics are consistent, but the formal claim requires proof.","section":"Sections 5.1-5.3, Assumption 2 verification"}],"minor_comments":[{"comment":"The text contains a typo: 'how bitcoin sort operates' should be 'how bitonic sort operates'.","section":"Section 2.2"},{"comment":"The name 'Telgarsy' should be 'Telgarsky'.","section":"Section 3.1"},{"comment":"The first trigonometric identity has a typo: 'sin b' should be 'sin x'.","section":"Section 3.4, Eq. (11)"},{"comment":"The expression for \\tilde c(x) is written with beta in the text preceding Eq. (20), but Eq. (20) and the subsequent discussion use gamma. These should be made consistent.","section":"Section 4.3, after Eq. (18)"},{"comment":"The text refers to 'Algorithm 11' when it means 'Algorithm 7', and 'approxiation' should be 'approximation'.","section":"Section 5.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a useful constructive study of ReLU network expressivity, and the code availability is a significant plus. The central indexing error in Theorem 3.1 and the sign errors in Section 4 are fixable, but they are load-bearing and must be addressed before the paper can be accepted. I would also encourage the author to consider whether the title's generality ('the algorithmic construction of deep ReLU networks') overstates the paper's scope, which is really a collection of explicit constructions plus a conditional-compilation framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper is worth reading, but the central folding theorem as printed is false. The mistake is an indexing error and the core constructions survive the correction, but it must be fixed before the paper is cited as a proof.\n\nThe genuinely new material is the exact min/max comparison element, the exact bitonic sorting network with deterministic wiring, and the conditional-branching compiler based on crossing functions. The x^2 construction is explicitly a re-derivation of Telgarsky, which the author honestly says; that is fine. The folding/unfolding networks for exp, trig functions, monomials, and xy appear to be new, are built from first principles, and come with a public Julia package plus numerics matching the stated 2^{-2L} error rates. That is real evidence and it earns credit.\n\nThe problem is in Section 3.2. Equation (10) defines f_L as the sum of eta_j(p_j(x)), where p_j is the j-fold composition, and Theorem 3.1 says x^2 - f_L = p_L^2. With that definition, the theorem is false. For L=1 it yields f_1 = eta_1(h_1(x)) which is identically zero on [0,1], so the claimed error p_1^2 is wrong. What is true is x^2 = p_L^2 + sum_{j=1}^L eta_j(p_{j-1}(x)), with p_0 = x. So the displayed theorem and the proof identity need p_{j-1} instead of p_j in the sum. This is a one-line fix, but it matters: the later exp, sin/cos, monomial, and multiplication algorithms share the same unfolding structure, so the formal rate proofs inherit the defect until the statement is corrected.\n\nTwo smaller issues. First, Assumption 2 (the crossing assumption) is reasonable, but the paper only verifies it for the first level and says the later levels are analogous. A complete proof for every j would be better. Second, the abstract claims the sorting network 'has optimal computational complexity' in some sense, but no lower bound is given. Bitonic wiring is deterministic and parallel, but 'optimal' is not established by the depth count alone.\n\nRecommendation: send it to peer review. The author should fix Theorem 3.1 and add a short proof of the crossing inequalities for all levels. The intended audience — people working on constructive expressivity and algorithms-as-networks — will get substantial value from the corrected version, and I would cite it.","headline":"A genuinely constructive ReLU toolbox with a real but fixable indexing bug in its central folding theorem.","tokens_in":18932,"tokens_out":2873,"would_cite":true,"duration_ms":30194,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","41A30","41A25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A ReLU network can be explicitly programmed to sort exactly and to approximate smooth functions with exponentially small error.","keywords":["ReLU networks","algorithmic construction","exact sorting","bitonic sort","conditional branching","folding and unfolding","function approximation","recursive algorithms"],"falsifier":"Build the continuous if-then-else with $a(x)=x$, $b(x)=1+\\sqrt{|x|}$, $c(x)=1-\\sqrt{|x|}$, so both branches agree at $x=0$. On a dense grid near $0$, evaluate the right-hand side of (20) with any finite positive $\\beta,\\gamma$: for $x>0$ it returns $1+\\beta x$ instead of $1+\\sqrt{x}$, so the compiled network cannot represent the statement. For the paper's own networks, one can verify the displayed inequalities for $\\beta_j,\\gamma_j$ at every level $j$ on a fine grid; any violation would show up as an output error on some interval.","tokens_in":17864,"feed_emoji":"🧮","tokens_out":12873,"duration_ms":127153,"temperature":0.7,"pith_summary":"This paper claims that a feedforward ReLU network can be built by programming rather than training: from a description of an algorithm, one can write down exact weights that make the network carry it out. The headline examples are an exact sorting network for 16,384 inputs and recursive folding constructions that approximate $e^x$, $\\cos x$, $\\sin x$, monomials, and $xy$ with error that scales like $2^{-2L}$ in the number of levels. If the claim is right, neural networks can serve as transparent, analyzable algorithms whose approximation rates are proven rather than fitted. The paper's answer to what ReLU networks can represent is constructive: a class of continuous conditional branching can be compiled into explicit ReLU layers.","feed_headline":"Programmed ReLU nets sort exactly, track e^x and cos x","feed_subtitle":"Folding and unfolding turn if-then-else checks into transparent deep networks with provable error.","key_machinery":"The load-bearing object is the conditional-branching identity (20), which expresses the output of an if-then-else as a sum of ReLU terms: $z(x)=b(0)-\\operatorname{ReLU}(\\beta a(x)-\\hat b(x))+\\beta\\operatorname{ReLU}(a(x))+\\operatorname{ReLU}(-\\gamma a(x)+\\hat c(x))-\\gamma\\operatorname{ReLU}(-a(x))$, valid when $\\hat b$ crosses $\\beta a$ and $\\hat c$ crosses $\\gamma a$ at the critical point. It carries the argument because it converts algorithmic branching into fixed weights, so recursive algorithms (sorting, folding, unfolding) become explicit networks. Around it, the comparison element $\\mathrm{minmax}(x,y)=A_1\\operatorname{ReLU}(A_2x)$ and the folding/unfolding relations (9), (21) provide the concrete building blocks for sorting and function approximation.","core_discovery":"The paper's central discovery is a compilation scheme: any continuous if-then-else statement of the form 'if $a(x)\\ge 0$ then $b(x)$ else $c(x)$' can be realized exactly by a fixed linear combination of ReLU calls, as long as the normalized branch functions $\\hat b,\\hat c$ cross a fixed multiple of $a$ at the critical point (Assumption 2, identity (20)). This turns recursive algorithms into deep ReLU networks layer by layer. The same scheme gives an exact neural sorting network by wiring min and max comparison elements in a bitonic network, with depth $O(\\log^2 N)$ and $O(N\\log^2 N)$ nonzero parameters. For smooth univariate functions, folding operations $h_j(x)=2^{-j}-|x-2^{-j}|$ reduce the approximation to a tiny interval, and unfolding adds correction terms that are themselves ReLU-linear; the paper proves the resulting error is exactly $p_L(x)^2$ for $x^2$ and $O(2^{-2L})$ for the other examples. The networks are sparse, recursive, parallel at each layer, and fully transparent.","pith_inferences":["Beyond the paper, the crossing constants $\\beta,\\gamma$ could in principle be learned from function samples instead of derived analytically, which would turn the compilation scheme into a practical tool for other algorithms.","The exact min/max comparison elements could serve as fixed, understood building blocks for rank-based operations in larger networks, since they are continuous and piecewise linear.","Any univariate function with a known shift identity should admit a similar folding/unfolding construction; testing functions such as $\\log(1+x)$ or special functions would map the real boundary of the method.","Because all examples here are sparse, the paper does not explain dense deep networks; the algorithmic view suggests dense networks must couple quantities across many scales, which is left open."],"forward_implications":["Exact sorting with ReLU is possible: a network with depth $O(\\log^2 N)$ and $O(N\\log^2 N)$ nonzero parameters returns the sorted input exactly, not approximately.","The same conditional-branching compilation makes the paper's approximations provable: the error for $x^2$ is exactly $p_L(x)^2$ and the error for exp, cos, sin, monomials, and xy is bounded by $O(2^{-2L})$.","Because recursion depth equals network depth, increasing the number of levels improves accuracy and requires correspondingly deeper networks; deep networks outperform shallow ones in these constructions.","A single if-statement inside a recursive fold can generate exponentially many linear pieces, showing how compact algorithmic descriptions translate into high expressivity.","The constructed networks are sparse and fully transparent: every weight, bias, and layer has a known role in the underlying algorithm, so no training is needed."],"supporting_citations":[{"why":"Supplies the bitonic sorting network whose comparison structure the neural network mirrors layer by layer.","marker":"[1]"},{"why":"Establishes the neural sorting network context the paper enters, but only with approximate sorting, which the exact construction improves on.","marker":"[18]"},{"why":"Supplies the sawtooth-function representation of x^2 that Section 3 folds and unfolds.","marker":"[23]"},{"why":"Supplies the identity xy = ((x+y)^2 - x^2 - y^2)/2 and the ReLU approximation framework used for polynomials and smooth functions.","marker":"[26]"},{"why":"Provides the classical algorithmic validation of bitonic sort that underlies the exactness argument.","marker":"[10]"},{"why":"Supplies the calculus of networks used to concatenate and rewire network blocks in the implementations.","marker":"[19]"}],"fun_headline_variants":["ReLU nets as algorithms: exact sort, fold, unfold","Constructive ReLU nets sort exactly, recurse deeply","Deep ReLU nets: recursive algorithms, exact sorting","Algorithmic ReLU nets: bitonic sort, provable depth","ReLU networks compiled from if-then-else logic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction depends on a geometric crossing condition: at every branch point, each branch function must straddle a fixed multiple of the condition function, rather than merely touching or flattening there; if that condition fails on any level, equation (20) can deliver the wrong branch on some interval.","fun_headline_variants_meta":{"raw":{"variants":["ReLU nets as algorithms: exact sort, fold, unfold","Constructive ReLU nets sort exactly, recurse deeply","Deep ReLU nets: recursive algorithms, exact sorting","Algorithmic ReLU nets: bitonic sort, provable depth","ReLU networks compiled from if-then-else logic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1254,"prompt_tokens":986,"completion_tokens":268,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":185}},"tokens_in":602,"tokens_out":268,"duration_ms":3086,"temperature":1.0,"reasoning_tokens":185,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:38:14.833837+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the continuous if-then-else with $a(x)=x$, $b(x)=1+\\sqrt{|x|}$, $c(x)=1-\\sqrt{|x|}$, so both branches agree at $x=0$. On a dense grid near $0$, evaluate the right-hand side of (20) with any finite positive $\\beta,\\gamma$: for $x>0$ it returns $1+\\beta x$ instead of $1+\\sqrt{x}$, so the compiled network cannot represent the statement. For the paper's own networks, one can verify the displayed inequalities for $\\beta_j,\\gamma_j$ at every level $j$ on a fine grid; any violation would show up as an output error on some interval.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the bitonic sorting network whose comparison structure the neural network mirrors layer by layer."},{"cited_title":"Petersen, C","cited_arxiv_id":null,"evidence_quote":"Establishes the neural sorting network context the paper enters, but only with approximate sorting, which the exact construction improves on."},{"cited_title":"Yarotsky","cited_arxiv_id":null,"evidence_quote":"Supplies the identity xy = ((x+y)^2 - x^2 - y^2)/2 and the ReLU approximation framework used for polynomials and smooth functions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the classical algorithmic validation of bitonic sort that underlies the exactness argument."},{"cited_title":"Petersen and F","cited_arxiv_id":null,"evidence_quote":"Supplies the calculus of networks used to concatenate and rewire network blocks in the implementations."}],"review_version":2}