betaFeedback

WorksComputer Science

Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification

Abstract

We study the iterates of a fixed ReLU network NN of width 4, that is, the discrete-time system xk+1=N(xk)x_{k+1} = N(x_k) on [0,1]4[0,1]^4. Equivalently, xkx_k is the output of a weight-tied network made of kk copies of NN, or of a recurrent network with no external input, started at x0x_0. We prove that every deterministic Turing machine MM admits such a network NMN_M. The network can be constructed in polynomial time from MM. Each iteration has depth poly(∣M∣)\mathrm{poly}(|M|). The iterates of NMN_M simulate MM exactly on every encoded tape. The number of iterations is proportional to the running time of MM. Moreover, the fourth coordinate irreversibly flags every point of the convex cube [0,1]4[0,1]^4 whose simulation reads an invalid digit. This flag is the certificate that makes hardness reductions sound on convex input regions, the regime of practical verifiers. Convex regions were previously inaccessible because of a continuity obstruction inherent to ReLU networks. The correspondence has three consequences. First, reachability for iterated width-4 ReLU networks spans the full complexity hierarchy along the single axis of the time bound: it is NP-complete for a unary bound, NEXP-complete for a binary bound and RE-complete (undecidable) with no bound. Second, two extra neurons of width suffice to extend the hardness to every common smooth activation: at width 6, the robust verification problem (a promise problem with δ/2δδ/2δ gap) is NP-complete for tanh⁡\tanh, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant. Third, the whole spectrum transfers to discretized Neural ODEs in dimension 5.

Introduction

We study the iterates of a fixed ReLU network of constant width: the discrete-time system

xk+1=N(xk),x0∈[0,1]4,x_{k+1}=N(x_k), \qquad x_0\in[0,1]^4,

where N:[0,1]4→[0,1]4N:[0,1]^4\to[0,1]^4 is a feedforward ReLU network of width 4. In other words, the object of study is a recurrent network that takes no per-step input: its input is its initial state x0x_0, and its outputs are its states xkx_k. Iterating one fixed block is the pattern behind deep equilibrium models [5] and discretized Neural ODEs [14, 24]. Residual and highway 40th Conference on Neural Information Processing Systems (NeurIPS 2026). networks [20, 37] follow the same pattern with untied weights. We ask what the iterates of a width-4 block can compute, and what it costs to verify their behavior.

The correspondence. We prove that iterated width-4 ReLU networks are Turing complete on convex input regions, with iteration count playing the role of time. For every Turing machine (TM) MM, we construct in polynomial time a single network NM:[0,1]4→[0,1]4N_M : [0,1]^4 \to[0,1]^4 of width 4 and depth poly⁡(∣M∣)\operatorname{poly}(|M|) per iteration. Its iterates simulate MM exactly on encoded tapes, and irreversibly flag every point of [0,1]4[0,1]^4 whose simulation reads an invalid digit (Theorem 3). Instantiated on a universal TM UU, the construction yields a single fixed block NUN_U that simulates every machine on every input. The consequence is a hardness ladder along the single axis of the time bound (Theorem 7). At fixed width 4, bounded-time reachability is NP-complete for a unary bound, NEXP-complete for a binary bound and undecidable with no bound. NP-hardness of ReLU verification has been known since Katz et al. [ [23]; the ladder shows that restricting the width does not restore tractability, since width 4 already suffices (§ 2.2). The hardness extends at width 6 to every common smooth activation (Theorem 10) and, through the correspondence of Duan et al. [ [15], to discretized Neural ODEs at dimension 5 (Theorem 50).

The obstruction, in plain terms. A TM tape is an infinite binary string, and to feed it to a network we must store it in a single real number. Writing the tape in base 2 fails twice over: 0.01‾2=0.120.0\overline{1}_2 = 0.1_2, so two different tapes can be the same number, and reading off the first bit is a discontinuous operation. Writing it in base 4 using only the digits 1 and 3, a device going back to Siegelmann and Sontag [ [34], repairs both defects. The encoding becomes injective, and the two possible leading digits are separated by a fixed gap, so a continuous piecewise-affine gadget can read the first digit. The price is that the valid encodings form a Cantor-like set DD1,3\mathbb{D}\mathbb{D}_{1,3} of measure zero, whereas verification asks a question about a full-dimensional convex region. The two domains cannot be reconciled by any continuous preprocessing: any continuous map from a convex set into DD1,3\mathbb{D}\mathbb{D}_{1,3} is constant (Proposition 11), and ReLU networks compute only continuous piecewise-affine maps. Since continuous encoding is impossible, our network detects: a fourth coordinate accumulates, one base-4 digit per iteration, a continuous certificate that irreversibly flags every input whose simulation reads an invalid digit. This online certificate is the ingredient that is new at the level of network construction. It is what makes every verification reduction below sound on convex regions.

Four theorems. Formal statements are in Section 2, proofs in the appendices.

(Th.3) Turing completeness of iterated width-4 networks on convex input spaces. For every TM MM, a single polynomial-time-constructible width-4 ReLU network simulates MM when iterated, exactly on encoded inputs, and irreversibly flags every point of the convex cube [0,1]4[0,1]^4 whose simulation reads an invalid digit.

(Th.7) Verification spectrum. Bounded-time reachability for iterated width-4 ReLU networks is NP-complete with unary time bound, NEXP-complete with binary time bound and RE-complete (undecidable) with no bound.

(Th.10) Robust verification at width 6 for smooth activations. For every continuous, non-polynomial, C1C^1-at-a-point, polynomial-time-computable activation ρ\rho, the δ\delta-robust verification problem (a promise problem with δ/2δ\delta/2^\delta gap) for width-6 ρ\rho-networks is NP-complete.

(Th.50) Neural ODE consequences at dimension 5 (App.H). Through the correspondence of Duan et al. [ [15] between vanilla feedforward networks and splitting-method discretizations, the whole spectrum transfers to the discretized reachability of Neural ODEs at dimension 5.

Positioning. Table 1 situates the results; its mode column records whether a statement concerns a feedforward network or the iterates of one (a recurrent network). Siegelmann–Sontag Siegelmann [1999], Siegelmann and Sontag [1991, 1994] established TM universality for recurrent networks; in the variant relevant here, where the input is placed in the initial state, their construction requires fractal-encoded inputs and does not optimize width. (Their results with per-step input sequences carry no such restriction, but answer a different question.) Bounded-width approximation by feedforward networks was developed by Hanin and Sellke [ [19], Park et al. [ [31], Telgarsky [ [38]. Bournez et al. [ [11] contains two distinct results: a width-3 network simulating one TM step exactly on the fractal encoding set, and a separate width-12 uniform approximation theorem for arbitrary continuous piecewise-affine maps on convex domains. Theorem 3 improves neither width. It establishes a different property: a single width-4 network whose iterates are exact on encoded inputs and certify non-encoded inputs, uniformly over the whole convex cube [0,1]4[0,1]^4 (§ 3.1 explains why neither prior result yields this). Verification of ReLU networks was previously known to be NP-hard via SMT-style encodings Katz et al. [ [23]; (Th. 7) lifts this to the full NP / NEXP / RE spectrum along the time bound, and (Th. 10) extends it to smooth activations at width 6. Training hardness is known up to ∃\existsR-completeness Blum and Rivest [ [8], Abrahamsen et al. [ [1], Froese et al. [ [16]. The question we study is also the narrow-network analogue of a line of work on how expressive power grows with the number of sequential steps: Merrill and Sabharwal [ [28] show that transformers gain expressive power as the number of chain-of-thought steps grows, and ours is the same trade-off in a different architecture class, pushed to its limit. Finally, the Neural ODE consequence (Th. 50) uses the discrete-to-continuous correspondence Chen et al. [ [14], Duan et al. [ [15].1

modeinput domainguaranteewidthactivation
Siegelmann–Sontag [1991, 1994, 1999]recurrentfractal D1,3\mathbb{D}_{1,3}exact TM simulationnot optimizedsaturated linear
Hanin and Sellke [2017]feedforwardcompact Rd\mathbb{R}^duniform approx.d+1d+1 to d+4d+4ReLU
Park et al. [2020]feedforwardcompact Rd\mathbb{R}^duniform approx.d+1d+1 to d+4d+4ReLU
Bournez et al. [2025], main thm.feedforwardconvex [0,1]d[0,1]^duniform approx. of CPAMs12ReLU
Bournez et al. [2025], Thm. 23iteratedfractal D1,3\mathbb{D}_{1,3}exact TM step; no claim off fractal3ReLU
Bournez et al. [2026]iteratedfractal + convexNP-hardness via 3-SAT3, 4ReLU
this paper, Th. 3iteratedconvex [0,1]4[0,1]^4exact TM simulation + certificate4ReLU
this paper, Th. 10bothconvex [0,1]d[0,1]^drobust verif. NP-c.6smooth ρ\rho

Table 1. Positioning. The mode column distinguishes feedforward statements from statements about the iterates of a fixed block. (Th. 3) improves neither width of Bournez et al. [ [11]: it is the first exact TM simulation whose soundness extends to a full-dimensional convex input region, which is what the NEXP and undecidability statements require.

Model, problems, and main theorems

Networks, iteration, and verification

The model: iterated networks. The object of study in Theorems 3 and 7 is the discrete-time system xk+1=N(xk)x_{k+1}=N(x_k) obtained by iterating a fixed feedforward ReLU network N:[0,1]4→[0,1]4N:[0,1]^4\to[0,1]^4 of width 4. In other words, it is a weight-tied recurrent network that takes no per-step input: its input is its initial state and its outputs are its states. We write N[t]:=N∘N∘⋯∘NN^{[t]} := N \circ N \circ\cdots\circ N for the tt-fold composition. Which representation a result concerns is stated with the result: the unary-bound NP-completeness also holds for feedforward width-4 networks, by unrolling (Corollary 8), while the NEXP and RE statements concern the iterated representation, whose unrolled depth would be exponential or unbounded.

We consider neural networks with rational weights, with the “enhanced neuron” convention (e.g. Kidger and Lyons [ [25]): a neuron is a map ψ∘ρ∘ϕ\psi\circ\rho\circ\phi with ϕ,ψ\phi,\psi affine and ρ\rho the activation. We write Nn,m,kρ\mathcal{N}^{\rho}_{n,m,k} for the class of feedforward networks with nn inputs, mm outputs, ρ\rho activation, and bounded width kk (i.e. every hidden layer has at most kk neurons).

Verification problems. Our hardness results concern the following decision problems.

Definition 1 (Reachability). The reachability problem takes as input a ρ\rho-network N:[0,1]d→[0,1]dN:[0,1]^d\to[0,1]^d and two convex regions Init,Acc⊆[0,1]d\mathrm{Init},\mathrm{Acc}\subseteq[0,1]^d specified by rational linear inequalities, and asks whether ∃x∈Init, ∃t≥0, N[t](x)∈Acc\exists x\in\mathrm{Init},\ \exists t\geq0,\ N^{[t]}(x)\in\mathrm{Acc}.

Here, the network is presented as a weighted graph, where the encoding of each hidden layer is the adjacency matrix, but every entry is the numerator-denominator-pair describing the rational weight. This formulation follows the standard one in the neural-network verification literature (see e.g. Katz et al., [23], Wurm, [41]).

Definition 2 (Bounded-time reachability). The TT-bounded reachability problem takes the same input plus a time bound T∈NT \in\mathbb{N} (encoded either in unary or in binary) and asks whether ∃x∈Init, ∃t≤T, N[t](x)∈Acc\exists x \in\mathrm{Init},\ \exists t \le T,\ N^{[t]}(x) \in\mathrm{Acc}.

When ρ=ReLU⁡\rho= \operatorname{ReLU}, both problems admit NP-membership for unary TT: by the small-witness property for piecewise-affine systems (Lemma 36, classical), it suffices to guess a rational xx of polynomial bit complexity and simulate TT steps with exact rational arithmetic. For binary TT, no such polynomial-time simulation exists; we recover NEXP-membership in § 4.

Why reachability, why convex regions, why iterates

Robustness certification is exactly the reachability question we study: an ℓ∞\ell_\infty ball around a data point xˉ\bar{x} is an axis-aligned box, hence a convex polytope specified by rational linear inequalities, and the certification query is literally ∃x∈Init:N(x)∈Acc\exists x \in\mathrm{Init}: N(x) \in\mathrm{Acc}, with Acc\mathrm{Acc} the region where the decision is wrong. This is the VNN-LIB and VNN-COMP specification format [13], decided by complete verifiers such as Reluplex, Marabou and α,β\alpha,\beta-CROWN [23, 40]. Convex initial regions are therefore imposed by the application. Iteration matters wherever one block is applied repeatedly, above all in closed-loop verification of a neural controller, where the reachable set over kk control steps is exactly N[k](Init)N^{[k]}(\mathrm{Init}). The practical reading of our results is that certification cost scales along depth, or number of steps, and not along width: at width 4, relaxing only the time bound climbs PTIME →\to NP →\to NEXP →\to undecidable, and the remaining route to tractability is a restriction on the dynamics or on the parameters (§ 6).

Encoding Turing machines

We encode Turing-machine (TM) configurations using base-4 digits {1,3}\{1,3\}, a Cantor-style encoding in the lineage of Siegelmann and Sontag [ [34, 35]. Allowing all digits would create ambiguities like 0.13‾4=0.24‾40.1\overline{3}{}_4 = 0.2\overline{4}{}_4; restricting to digits 1 and 3 makes the presentation of a number unique, and resolves the discontinuity issues inherent to ReLU iteration. A word u=u1⋯un∈{0,1}nu = u_1 \cdots u_n \in\{0,1\}^n maps to enc⁡{1,3}(u)=∑i=1n(2ui+1)4−i∈[0,1]\operatorname{enc}_{\{1,3\}}(u) = \sum_{i=1}^{n}(2u_i + 1)4^{-i} \in[0,1]. A configuration c=(u,q,v)c = (u,q,v) (current state qq, tape to the left of the head uu (reversed), tape from the head onward vv) is encoded as

enc⁡M(c)=(enc⁡{1,3}(u),enc⁡M(q,v),0,0)∈[0,1]4.\operatorname{enc}_M(c) = \left(\operatorname{enc}_{\{1,3\}}(u),\operatorname{enc}_M(q,v),0,0\right) \in[0,1]^4.

where enc⁡M(q,v)\operatorname{enc}_M(q,v) co-encodes the state and the right tape into a single base-4 string with enc⁡M(q)\operatorname{enc}_M(q) as a constant-length prefix followed by enc⁡{1,3}(v)\operatorname{enc}_{\{1,3\}}(v), based on a packing borrowed from Bournez et al. [2025] that saves one coordinate over the naive encoding (enc({1,3})(u)(\{1,3\})(u), enc{1,3}(v)_{\{1,3\}}(v), encM(q)_M(q), ⋯\cdots) which would force width 5. The third coordinate is a scratch register used by the simulator; the fourth is a validity register, both initially 0 (see § 4). We write QQ for the state set of MM, enc⁡M(Q)⊆[0,1]\operatorname{enc}_M(Q) \subseteq[0,1] for the prefix-encoded set of states, DDD⁡1,3⊆[0,1]\operatorname{DDD}_{1,3} \subseteq[0,1] for the Cantor-like set of points whose base-4 expansion uses only digits {1,3}\{1,3\}, τ∈{0,1}ω\tau\in\{0,1\}^{\omega} for the infinite input, step⁡M\operatorname{step}_M for the map sending a configuration of MM to the next one, and ct(τ):=step⁡Mt(c0(τ))c_t(\tau) := \operatorname{step}_M^t(c_0(\tau)) for the configuration at step tt on an infinite tape τ∈{0,1}ω\tau\in\{0,1\}^{\omega}, with c0(τ)c_0(\tau) the initial configuration. The state prefix of x2x_2 consists of its first ∣q∣4=⌈log⁡4∣Q∣⌉\lvert q\rvert_4 = \lceil\log_4 \lvert Q\rvert\rceil base-4 digits, and the post-state-prefix (or tape-suffix) portion of x2x_2 is the remainder. We say that a digit of x1x_1, or of the tape-suffix of x2x_2, is visited during the first kk iterations of the network of Theorem 3 if it is exposed as the leading digit of its register at some iteration j<kj < k. When xx encodes a configuration, the visited digits are exactly the tape cells read by MM’s head.

Turing completeness of iterated width-4 networks on convex input spaces

Theorem 3 (Turing completeness on convex input spaces). For every deterministic Turing machine MM over the binary alphabet, one can construct in polynomial time a single ReLU⁡\operatorname{ReLU} network NM:[0,1]4→[0,1]4N_M : [0,1]^4 \to[0,1]^4 of width 4 and depth DM=poly⁡(∣M∣)D_M = \operatorname{poly}(\lvert M\rvert), with a constant CM∈NC_M \in\mathbb{N}, such that:

(i) (Faithful simulation, all time.) For every τ∈{0,1}ω\tau\in\{0,1\}^{\omega} and every t≥0,t \ge0,

NM[CMt](enc⁡M(c0(τ)))=enc⁡M(step⁡Mt(c0(τ))).N_M^{[C_Mt]}\left(\operatorname{enc}_M(c_0(\tau))\right) = \operatorname{enc}_M\left(\operatorname{step}_M^t(c_0(\tau))\right).

(For finite inputs ww, take τ=w⋅τ′\tau= w \cdot\tau' for any suffix τ′\tau'; MM’s behavior up to time TT depends only on the first ≤T\le T symbols.)

References

  1. [1]Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks ∃R-complete. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, volume 34, pages 18293–18306, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/9813b270ed0288e7c0388f0fd4ec68f5-Abstract.html.arxiv.org/abs/2102.09798
  2. [2]Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. CoRR, abs/1611.01491, 2016. doi: 10.48550/arXiv.1611.01491. URL http://arxiv.org/abs/1611.01491.
  3. [3]Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. ISBN 978-0-521-42426-4. doi: 10.1017/cbo9780511804090. URL http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.DOI
  4. [4]Eugene Asarin, Oded Maler, and Amir Pnueli. Reachability analysis of dynamical systems having piecewise-constant derivatives. Theoretical Computer Science, 138(1):35–65, feb 1995. ISSN 0304-3975. doi: 10.1016/0304-3975(94)00228-B.
  5. [5]Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019), 2019. doi: 10.48550/arXiv.1909.01377.DOI
  6. [6]Hugo Bazille, Olivier Bournez, Walid Gomaa, and Amaury Pouly. On the complexity of bounded time reachability for piecewise affine systems. In Joël Ouaknine, Igor Potapov, and James Worrell, editors, Reachability Problems - 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings, volume 8762 of Lecture Notes in Computer Science, pages 20–31. Springer, 2014. doi: 10.1007/978-3-319-11439-2\_2. URL https://doi.org/10.1007/978-3-319-11439-2\_2.
  7. [8]Avrim Blum and Ronald L. Rivest. Training a 3-node neural network is np-complete. In David S. Touretzky, editor, Advances in Neural Information Processing Systems 1, [NIPS Conference, Denver, Colorado, USA, 1988], volume 1, pages 494–501. Morgan Kaufmann, 1988. doi: 10.1016/s0893-6080(05)80010-3. URL http://papers.nips.cc/paper/125-training-a-3-node-neural-network-is-np-complete.
  8. [10]Olivier Bournez, Manuel Lameiras Campagnolo, Daniel Silva Graça, and Emmanuel Hainry. Polynomial differential equations compute all real computable functions on computable compact intervals. Journal of Complexity, 23(3):317–335, June 2007. doi: 10.1016/j.jco.2006.12.005. URL http://dx.doi.org/10.1016/j.jco.2006.12.005.
  9. [11]Olivier Bournez, Johanne Cohen, and Adrian Wurm. A universal uniform approximation theorem for neural networks. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, August 25-29, 2025, volume 345 of LIPIcs, pages 29:1–29:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. ISBN 978-3-95977-388-1. doi: 10.4230/LIPIcs.MFCS.2025.29. URL https://doi.org/10.4230/LIPIcs.MFCS.2025.29.
  10. [12]Olivier Bournez, Johanne Cohen, Laura Cohen, and Adrian Wurm. Fractal gadgets for neural networks: The complexity of the narrow regime. In 46th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’2026), December 2026.arxiv.org/abs/2610.06092
  11. [13]Christopher Brix, Mark Niklas Müller, Stanley Bak, Taylor T. Johnson, and Changliu Liu. First three years of the international verification of neural networks competition (VNN-COMP). International Journal on Software Tools for Technology Transfer, 25(3):329–339, 2023. doi: 10.1007/s10009-023-00703-4.DOI
  12. [14]Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6572–6583, 2018. URL https://proceedings.neurips.cc/paper/2018/hash/69386f6bb1dfed8692a24c8686939b9-Abstract.html.arxiv.org/abs/1806.07366
  13. [15]Yifei Duan, Li’ang Li, Guanghua Ji, and Yongqiang Cai. Vanilla feedforward neural networks as a discretization of dynamical systems. Journal of Scientific Computing, 101(3):82, 2024. doi: 10.1007/s10915-024-02710-2. URL https://doi.org/10.1007/s10915-024-02710-2.
  14. [16]Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. J. Artif. Intell. Res., 74:1775–1790, 2022. doi: 10.1613/jair.1.13547. URL https://doi.org/10.1613/jair.1.13547.
  15. [17]Sicun Gao, Jeremy Avigad, and Edmund M. Clarke. Delta-decidability over the reals. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012, pages 305–314. IEEE, IEEE Computer Society, 2012. doi: 10.1109/LICS.2012.41. URL https://doi.org/10.1109/LICS.2012.41.
  16. [18]Oded Goldreich. On promise problems: A survey. In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254–290. Springer, 2006. doi: 10.1007/11685654\_12. URL https://doi.org/10.1007/11685654\_12.
  17. [19]Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. CoRR, abs/1710.11278, 2017. doi: 10.48550/arXiv.1710.11278. URL http://arxiv.org/abs/1710.11278.
  18. [20]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770–778. IEEE Computer Society, 2016. doi: 10.1109/CVPR.2016.90. URL https://doi.org/10.1109/CVPR.2016.90.
  19. [21]Helge Holden, Kenneth H Karlsen, Knut-Andreas Lie, and Nils Henrik Risebro. Splitting methods for partial differential equations with rough solutions. European Mathematical Society, 7:12, 2010.DOI
  20. [23]Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Repluplex: An efficient smt solver for verifying deep neural networks. In International conference on computer aided verification, pages 97–117. Springer, 2017.arxiv.org/abs/1702.01135
  21. [24]Patrick Kidger. On neural differential equations. CoRR, abs/2202.02435, 2022. doi: 10.48550/arXiv.2202.02435. URL https://arxiv.org/abs/2202.02435.
  22. [25]Patrick Kidger and Terry J. Lyons. Universal approximation with deep narrow networks. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2306–2327. PMLR, PMLR, 2020. URL http://proceedings.mlr.press/v125/kidger20a.html.
  23. [26]Pascal Koiran, Michel Cosnard, and Max H. Garzon. Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132(2):113–128, sep 1994. ISSN 0304-3975. doi: 10.1016/0304-3975(94)90229-1. URL https://doi.org/10.1016/0304-3975(94)90229-1.
  24. [27]Angus Macintyre, Alex J Wilkie, and P Odifreddi. On the decidability of the real exponential field. Kreisel’s Mathematics, 115:451, 1996.
  25. [28]William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations (ICLR 2024), 2024. doi: 10.48550/arXiv.2310.07923.DOI
  26. [31]Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. CoRR, abs/2006.08859, 2020. doi: 10.48550/arXiv.2006.08859. URL https://arxiv.org/abs/2006.08859.
  27. [32]Alexander Schrijver. Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999. ISBN 978-0-471-98232-6. doi: 10.2307/253980.DOI
  28. [34]Hava T. Siegelmann and Eduardo D. Sontag. Turing computability with neural nets. Applied Mathematics Letters, 4(6):77–80, 1991. doi: 10.1016/0893-9659(91)90080-f.DOI
  29. [35]Hava T. Siegelmann and Eduardo D. Sontag. Analog computation via neural networks. Theoretical Computer Science, 131(2):331–360, sep 1994. ISSN 0304-3975. doi: 10.1016/0304-3975(94)90178-3. URL https://doi.org/10.1016/0304-3975(94)90178-3.
  30. [36]Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997. ISBN 978-0-534-94728-6.DOI
  31. [37]Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks. CoRR, abs/1505.00387, 2015. doi: 10.48550/arXiv.1505.00387. URL http://arxiv.org/abs/1505.00387.
  32. [38]Matus Telgarsky. Benefits of depth in neural networks. In COLT, pages 1517–1539, 2016.arxiv.org/abs/1602.04485
  33. [39]Hale F. Trotter. On the product of semi-groups of operators. Proceedings of the American Mathematical Society, 10(4):545–551, 1959.DOI
  34. [40]Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. Beta-CROWN: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 29909–29921, 2021.
  35. [41]Adrian Wurm. Complexity of reachability problems in neural networks. In International Conference on Reachability Problems, pages 15–27. Springer, 2023a.DOI
  36. [42]Adrian Wurm. Complexity of reachability problems in neural networks. CoRR, abs/2306.05818, 2023b. doi: 10.48550/arXiv.2306.05818. URL https://doi.org/10.48550/arXiv.2306.05818.
  37. [43]Adrian Wurm. Robustness verification in neural networks. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 263–278. Springer, 2024.DOI
  38. [44]Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. Deep network approximation: Beyond ReLU to diverse activation functions. Journal of Machine Learning Research, 25(35):1–39, 2024.arxiv.org/abs/2307.06555

Paper details

vlnc:W_ywghaph5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents