betaFeedback

WorksComputer Science

A Witnessing Duality for ReLU Network Depth

Abstract

A depth lower bound for ReLU networks asserts that every sufficiently shallow network fails on some input. What does a proof of such a bound compute? We study this question for exact computation of the maximum of nn real inputs, with depth measured by the number of hidden layers. For every separately fixed prime qq and depth bound KK, we give a uniform TC0\mathsf{TC}^0 refuter for rational networks with at most KK hidden layers and more than qKq^K inputs, provided that the reduced denominators of their nonbias weights are not divisible by qq. Biases may be arbitrary rationals. The refuter finds a rational input on which the network fails, and its correctness is provable in VTC0\mathbf{VTC}^0, the bounded-arithmetic theory of uniform constant-depth threshold computation. The underlying numerical depth lower bound follows from Averkov, Hojny and Merkert (ICLR 2025), extending Haase, Hertrich and Loho (ICLR 2023); our contribution is an internal proof that makes its geometric argument into a feasible refuter. On the construction side, VTC0\mathbf{VTC}^0 verifies locally checkable certificates for the balanced integer-weight maximum network of depth ⌈log⁡2n⌉\lceil\log_2 n\rceil. At q=2q=2, the construction and refuter meet: for each fixed KK, the theory verifies that integer-nonbias-weight networks with arbitrary rational biases can compute the maximum with at most KK hidden layers exactly when n≤2Kn\le 2^K. We also give certified rational constructions of polynomial encoding length and depth O(log⁡n/log⁡log⁡n)O(\log n/\log\log n). These results instantiate a witnessing duality: bounded proofs of certified existence and of refutation correspond, respectively, to threshold-computable constructors and refuters whose guarantees the theory proves.

Introduction

A depth lower bound for neural networks guarantees that every shallower network fails on some input. Such a guarantee need not say how to find a failing input, and a feasible algorithm that finds one is a refuter for the bound. We study when a weak arithmetic theory can prove that a refuter succeeds, and compare this with its ability to certify explicit constructions. This computational content of lower bounds also motivates work on constructive separations and refuter problems [7, 13].

Our target is the exact representation of MAXn(x)=max⁡{x1,…,xn}\mathrm{MAX}_n(x)=\max\{x_1,\ldots,x_n\} by rational ReLU networks on Rn\mathbb{R}^n. Depth counts hidden layers, and the output is affine. The nonbias weights are the entries of the weight matrices, including the output weights, as opposed to the biases. For this target, the weight arithmetic determines whether depth is an obstruction.

With unrestricted rational weights, two hidden layers suffice [5 TR26], so for such weights there is no growing-depth lower bound to witness. By contrast, Haase, Hertrich and Loho proved that integer weights require logarithmic depth [16], and Averkov, Hojny and Merkert extended the bound to weights whose denominators are powers of a fixed integer [2]. The bound of Averkov, Hojny and Merkert requires that a fixed prime qq not divide the fixed integer, and the resulting depth bound is logarithmic to base qq. If the reduced denominators of all nonbias weights of a network omit qq, then their product is not divisible by qq and every nonbias weight is an integer divided by a power of this product, so the bound applies to the network. Thus this modular obstruction applies whenever the reduced nonbias denominators omit a fixed prime qq, and rational biases remain unrestricted.

For the maximum, we show that VTC0\mathrm{VTC}^{0}, the bounded-arithmetic theory of uniform constant-depth threshold computation, can both prove a refuter correct and certify explicit constructions. Our main technical result is on the refutation side: for every separately fixed prime qq and hidden-depth cap K≥1K \ge1, the theory proves the known modular depth lower bound together with the correctness of a specified refuter, which is itself a uniform constant-depth threshold computation. The refuter handles networks with more than qKq^{K} inputs, at most KK hidden layers, and nonbias weights whose reduced denominators omit qq (in particular, integer nonbias weights), with arbitrary rational biases.

On the construction side, uniformly in nn, the theory verifies a certified balanced integer-weight construction, described below, with ⌈log⁡2n⌉\lceil\log_{2} n\rceil hidden layers, which meets the refuter at q=2q=2. For each fixed KK, the theory thus witnesses both sides of a sharp threshold: with integer nonbias weights and arbitrary rational biases, at most KK hidden layers suffice exactly when n≤2Kn \le2^{K}. A second certified construction uses rational maximum blocks of slowly growing arity; the theory proves its correctness, verifies its complete rational evaluation histories (defined below), and proves a uniform depth inequality giving O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) hidden layers. Because depth alone does not measure description size, we also require polynomial total encoding length, including every matrix entry and its precision, and both constructions, together with their certificates, meet this requirement. Although two hidden layers suffice for unrestricted rational weights, none of the three known depth-two constructions, those of [5] and [TR26] and the blocks built here from the dictionary of [Zim26], is known to meet it (Appendix E.§ 3).

We work in VTC0\mathrm{VTC}^{0} as developed by Cook and Nguyen [9], with Jeřábek’s internal integer arithmetic [19]. The witnessing theorem for this theory turns a proof of a bounded existential assertion into a witnessing function computed by uniform constant-depth threshold circuits, an FTC0\mathrm{FTC}^{0} function, whose guarantee the theory proves. For real-input networks, applying it requires finite codes for networks and rational disagreements, explicit length bounds, and proofs that the finite tests express the intended all-real assertions (Appendix § 12 supplies the rational-witness bridge).

We apply witnessing in two directions, and call the resulting pair of correspondences the witnessing duality of the title. Bounded existence of a network together with a checkable certificate of its correctness, described below, corresponds to a threshold-computable constructor for which the theory proves that the output passes the check. A proof of the bounded assertion that every candidate network meeting the hypotheses has an error corresponds to a threshold-computable refuter for which the theory proves that the returned input is an error. Conversely, a constructor or refuter gives the corresponding existence theorem when the theory can prove its guarantee. The network-specific task is to supply sound checks, suitable bounds, and the internal proofs required by these correspondences.

The logical framework is standard, and the work lies in the concrete geometric and arithmetic constructions. The numerical lower bound is known; on the refutation side, the contribution is its internal geometric proof and the specified refuter.

The geometric argument iterates an intersection product of piecewise-linear functions over polyhedral cones (§ 3). It must be made finite: cone operations require explicit coordinates, divisibility requires actual integer quotients, and the contradiction must yield bounded rational test points. Every intermediate value is computed by an explicit parallel formula rather than by a loop over the input, so the refuter is a constant-depth threshold computation.

On the construction side, we give local certificates for assemblies of maximum gadgets, small fixed subnetworks that each compute the maximum of two values. The certificate labels each gadget by the input coordinates it aggregates, and local union checks verify these labels. Every gadget’s value can then be computed directly from the original inputs. An evaluation history records the rational value of every neuron, including the final output, and satisfies every equation between adjacent layers; with the labels, exact evaluation histories are available in parallel even when assembly depth grows.

In a related setting, Li, Li and Ren [21] study the reasoning needed for resolution lower bounds through the search for an error in a purported short proof. Here the candidate is a real-input network and the error is a rational point; on the upper side, the witness is a network with a locally checkable certificate.

Our Results

Table 1 summarizes the three main results.

ResultGuarantee
Internal modular refutationFor each fixed prime qq and depth cap KK, a specified FTC0^{0} refuter has VTC0^{0}-provable correctness for n>qKn > q^{K} when reduced nonbias denominators omit qq. Arbitrary rational biases and unreduced encodings are allowed (Theorem 8.5).
Certified integer constructionA uniform depth-⌈log⁡2n⌉\lceil\log_{2} n\rceil integer-weight family has polynomial total codes and full histories verified in VTC0^{0}. Combined with the prime-two refuter, it gives the sharp threshold n≤2Kn \le2^{K} for each fixed KK (Theorem 9.4 and Corollary 9.7).
Certified rational constructionPolynomial total network and certificate length and full histories, with a uniform internal depth inequality giving O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) hidden depth (Theorem 9.8 and Theorem C.1).

Table 1. The three main results; lower-bound primes and depth caps are fixed outside the input.

The main comparison in Table 1 pairs the modular refuter with the certified integer construction: at prime two they witness the two sides of the same sharp depth threshold in one theory. The third row extends the construction side to rational weights through short block certificates and exact substitution of the blocks into a balanced assembly. This gives a certified sublogarithmic-depth family whose correctness, histories and a uniform depth inequality are proved in the same theory.

The internal refuter. Fix a prime qq and an integer K≥1K \ge1, and write d=qKd = q^{K}. A rational weight is qq-free if its reduced denominator is not divisible by qq. The weights covered below are all matrix entries, including output weights; biases are exempt. A defining graph is a formula defining a function’s input-output relation. A function given together with its specified defining graph is called chosen, and a guarantee proved for it is a theorem about that graph.

Theorem 1.1 (Informal; restated as Theorem 8.5). For each separately fixed q,Kq,K, there is an FTC0^{0} function that, given a rational network NN on n≥qK+1n \ge q^{K}+1 inputs with at most KK hidden layers and qq-free nonbias weights, returns a rational nn-vector xx such that

N(x)≠max⁡ixi.N(x) \ne\max_i x_i.

One polynomial in the code length ∣N∣|N| of NN, independent of q,Kq,K, bounds the output length. With the function introduced by its specified defining graph, and with a fixed-depth network evaluator that rejects malformed inputs, VTC0^{0} proves the function’s guarantee and the corresponding bounded refutation sentence, which asserts that every such network has such a rational error. Stored rational fractions need not be reduced, and rational biases are arbitrary.

The function of Theorem 1.1 is chosen in this sense. Its circuit depth and the exponent of its polynomial size bound may depend on the externally fixed q,Kq,K, so the statement does not give a polynomial-time algorithm when the depth cap is part of the input. The output bound, by contrast, is one polynomial for all q,Kq,K; it comes from an explicit bound on the integer test points. The intermediate arrays of the construction have polynomial lengths whose degrees may depend on q,Kq,K, but these lengths do not enter the coordinates of the returned point. Widths and parameter magnitudes are unrestricted apart from the finite input encoding.

At q=2q = 2 the theorem covers integer nonbias weights, the setting of [16], and more generally rational weights whose reduced denominators are odd. For any fixed base β\beta coprime to qq, it covers weights in Z[1/β]\mathbb{Z}[1/\beta], the setting of [2 Theorem 2].

Certified constructions and two witnessing correspondences. For the positive direction we use local certificates that specify the input-coordinate set aggregated by each maximum gadget. The labels are supplied, rather than recovered from an arbitrary network. We prove that passing the local checks certifies exact maximum computation. The dimension nn is supplied to each constructor in unary.

Theorem 1.2 (Informal; restated as Theorem 9.3, Theorem 9.4 and Proposition 9.6). *There are chosen FTC0^{0} functions constructing, uniformly over n≥1n \ge1, an integer-weight network of hidden depth ⌈log⁡2n⌉\lceil\log_{2} n\rceil and an accepted maximum-assembly certificate. The theory VTC0^{0} proves acceptance and the certificate

checker’s soundness; supplied labels yield exact evaluation histories in FTC0\mathrm{FTC}^{0} even when assembly depth grows. More generally, a theorem of bounded existence of a network with an accepted certificate is equivalent to a chosen FTC0\mathrm{FTC}^{0} constructor for which the theory proves that the output is accepted. A theorem of bounded refutation, stated with a network evaluator defined in the theory, is likewise equivalent to a chosen FTC0\mathrm{FTC}^{0} refuter whose error guarantee the theory proves.

The equivalences use standard witnessing and the conservative extension of VTC0\mathbf{VTC}^{0} by chosen functions, with the specified checkers and bounds retained. They do not extract a network from the bare assertion that some network is correct on all inputs, which has an extra universal quantifier over inputs (see the Discussion below).

The concrete upper family is the classical balanced construction (cf. [1 Lemma D.3], whose two-input gadget uses weights ±1/2\pm1/2) with the integer gadget max⁡(a,b)=ReLU⁡(b−a)+ReLU⁡(a)−ReLU⁡(−a)\max(a,b) = \operatorname{ReLU}(b-a) + \operatorname{ReLU}(a) - \operatorname{ReLU}(-a), where ReLU⁡(t)=max⁡(t,0)\operatorname{ReLU}(t) = \max(t,0) is the ReLU. It has hidden depth ⌈log⁡2n⌉\lceil\log_{2} n \rceil, zero biases and nonbias weights in {−1,0,1}\{-1,0,1\}. At prime two, this construction and the refuter of Theorem 1.1 meet at the classical integer-depth boundary, whose lower bound is due to [16].

In the corollary below, representation is expressed by the fixed bounded correctness predicate of Corollary 9.7, which tests rational inputs up to a length cutoff; agreement on those inputs also characterizes agreement on all real inputs (Appendix § 12). The existential quantifier of Corollary 9.7 ranges over codes of length at most a fixed polynomial in nn whose nonbias weights are stored with denominator one, and the constructed network meets both conditions. This length bound enters the equivalence of Corollary 9.7; the refuter of Theorem 1.1 itself applies to candidates of every length.

Corollary 1.3 (Informal; restated as Corollary 9.7). For each separately fixed K≥1K \ge1, the theory VTC0\mathbf{VTC}^{0} verifies both sides of the sharp threshold: MAX⁡n\operatorname{MAX}_{n} has an integer-nonbias-weight representation of hidden depth at most KK exactly when n≤2Kn \le2^{K}. The positive side has the certified constructor of Theorem 1.2; above the threshold, every such candidate, with arbitrary rational biases, has the bounded rational error returned by the refuter of Theorem 1.1 at q=2q = 2.

The constructor is uniform across dimensions, whereas the refuter and its internal proof retain the externally fixed cap KK.

Certified rational compression. The integer family has a rational counterpart using maximum blocks of slowly growing arity, adapted from the dictionary construction of [Zim26]. We construct certified blocks directly and assemble them in a balanced network.

Theorem 1.4 (Informal; restated as Theorem 9.8 and Theorem C.1). There are chosen FTC0\mathrm{FTC}^{0} constructors for rational networks and certificates of polynomial total length. The theory VTC0\mathbf{VTC}^{0} proves their acceptance, exact MAX correctness, and one uniform integer inequality giving O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) hidden depth. For every rational input xx, a chosen FTC0\mathrm{FTC}^{0} function supplies a full evaluation history of length polynomial in n+∣x∣n + |x|, where ∣x∣|x| is the code length of xx, and the theory proves every adjacent evaluation equation.

The theorem does not assert polynomial size at depth two, and it claims no improvement in semantic size-depth bounds. Its contribution to the construction side is the certificate and history guarantee for this family, proved in Appendices B and C.

Quantified propositional proofs. Because V1\mathbf{V}^{1}, the bounded-arithmetic theory of polynomial-time reasoning, proves every theorem of VTC0\mathrm{VTC}^{0} (Lemma 2.4), the classical translation theorem for V1\mathbf{V}^{1} [9 Theorem 7.57] turns the internal proof of Theorem 1.1 into finite proof families. The tree-like quantified sequent calculus G1q\mathrm{G}_{1}^{q}, used here, restricts cut formulas to Σ1q∪Π1q\Sigma_{1}^{q} \cup\Pi_{1}^{q}; in this standard notation the superscript qq stands for quantified and is unrelated to the prime qq. The classes Σ1q\Sigma_{1}^{q} and Π1q\Pi_{1}^{q} are the smallest pair of classes that contain the quantifier-free formulas and are closed under conjunction and disjunction, with Σ1q\Sigma_{1}^{q} closed under existential and Π1q\Pi_{1}^{q} under universal Boolean quantification, and with negation taking each class into the other.

Corollary 1.5 (Informal; restated as Corollary 10.5). For fixed q,Kq,K and every input dimension and network-code length, the bounded assertion that each network meeting the hypotheses of Theorem 1.1 has the chosen refuter’s rational disagreement has a polynomial-size G1∗\mathbf{G}^{*}_{1} proof. A polynomial-time function generates these proofs from unary dimension and code-length parameters. For each network meeting the hypotheses, the satisfying existential assignments of this assertion decode to the chosen rational disagreement.

This is a proof-size upper bound for quantified translations of the refutation assertion. The conclusion of each proof still quantifies its counterexample existentially; no quantifier-free tautology encoding, bounded-depth threshold proof or proof-length lower bound is asserted.

The translation theorem is classical, and Appendix § 15 writes out the cases of its proof that the source leaves as exercises. Its proof in Cook and Nguyen’s book first puts the given proof in anchored form, in which every cut formula occurs in a non-logical axiom or in an induction instance. We use this anchoring step as stated; its proof in the book leaves the construction of a countermodel as an exercise [9 Exercise 6.44]. The application of the translation theorem rests on the internal geometric proof and on an explicit formula, in the original language, that retains the refuter’s output.

The certified balanced construction has the same propositional form: polynomial-size G1∗\mathbf{G}^{*}_{1} proofs, generated from 1n1^{n}, of a bounded assertion whose satisfying existential assignments for n≥1n \ge1 retain the balanced network and its certificate (end of § 10).

Unrestricted depth two. The blocks behind Theorem 1.4 also bear on the question of Appendix E: how much arithmetic suffices to prove that two hidden layers compute the maximum when the weights are unrestricted rationals. They answer it in VTC0\mathrm{VTC}^{0} up to padding (Corollary E.1). For every arity b≥2b \ge2 and every padding number n≥2771(b+1)5n \ge2^{771(b+1)^{5}} (here nn is a padding parameter, not the number of inputs), the theory proves that a chosen FTC0\mathrm{FTC}^{0} function of nn and bb returns a network with bb inputs, exactly two hidden layers and zero biases, together with a certificate that the cone-certificate checker of Appendix B.§ 1 accepts. It also proves that every evaluation history of this network at a rational input outputs the maximum of that input.

The padding number nn only makes room for the block: a threshold-computable function returns strings of length polynomial in its inputs, while the bounds we prove are 2512(b+1)22^{512(b+1)^{2}} on the code of the block for b≥3b \ge3 (Appendix C.§ 6; for b=2b=2 the block has three neurons in each hidden layer) and 2771(b+1)52^{771(b+1)^{5}} on the combined length of the block and its cone certificate (Lemma B.3). Adding the axiom EXPA\mathrm{EXP}_{A}, an instance of exponentiation stating that such an nn exists for every bb, removes the padding: VTC0+EXPA\mathrm{VTC}^{0}+\mathrm{EXP}_{A} proves the collapse at every arity (Corollary E.2). In the other direction, a proof of this unpadded collapse in a sound polynomial-bounded theory, such as VTC0\mathrm{VTC}^{0} or the union ⋃i<ωVi\bigcup_{i<\omega}\mathrm{V}^{i}, would yield depth-two networks for MAXb\mathrm{MAX}_{b} of total encoding length polynomial in bb (Corollary E.7 and the end of Section E.4.3). None of the three known constructions is known to have such a size (Appendix E.§ 3), and we do not decide whether such networks exist.

Together with Theorem 1.1, VTC0\mathrm{VTC}^{0} thus proves a form of each half of the opening observation that the weight arithmetic determines whether depth is an obstruction. For the lower bound, this is the bound with its refuter, for each fixed prime and depth, when the reduced nonbias denominators avoid the prime. For the collapse, it is the padded depth-two collapse for unrestricted rational weights, with correctness proved inside the theory at rational inputs.

Our Techniques

The refuter rests on the cone product, which we first illustrate in the plane and then use to explain the obstruction at two hidden layers. We then describe how the obstruction becomes a refuter and how the two certified constructions supply exact evaluation histories in parallel.

A planar view of the cone product. The cone product f∘Cf \circ C of a continuous piecewise-linear function ff with a weighted polyhedral cycle CC is a cycle of one lower dimension, supported where ff fails to be linear on CC and weighted by the jumps of its gradient, as in tropical intersection theory. A cycle is balanced if, around every face of codimension one, the weighted primitive normal vectors of the adjacent faces sum to zero modulo the span of that face.

The function g(x,y)=max⁡(0,x,y)g(x,y)=\max(0,x,y) gives a small example of the operation. Its gradient is 00, e1e_{1} or e2e_{2} in the three regions of Figure 1. Let UU be the planar unit cycle, with weight one on every two-dimensional chamber. The first product g⊙Ug \mathbin{\odot} U records the gradient jumps of gg. Its nonzero rays have the primitive integer directions below (their coordinates are coprime), each with lattice weight one:

Gradient regions of g(x,y) = max(0,x,y) and the three rays supporting its first cone product

Figure 1. Gradient regions of g(x,y)=max⁡(0,x,y)g(x,y)=\max(0,x,y) and the three rays supporting its first cone product. Primitive directions are marked; each displayed ray has lattice weight one in this example.

v1=(−1,0),v2=(0,−1),v3=(1,1).v_1=(-1,0),\qquad v_2=(0,-1),\qquad v_3=(1,1).

They balance because v1+v2+v3=0v_1+v_2+v_3=0. The second product is a scalar at the origin:

(g⊙(g⊙U))(0)=g(v1)+g(v2)+g(v3)=1.\bigl(g\mathbin{\odot}(g\mathbin{\odot} U)\bigr)(0)=g(v_1)+g(v_2)+g(v_3)=1.

The defining sum of the product subtracts one reference linear function evaluated at each ray, and these terms sum to zero because the rays balance. For rational a,ba,b, the ReLU of a single linear form, h(x,y)=max⁡(0,ax+by)h(x,y)=\max(0,ax+by), has its first product supported on the line ax+by=0ax+by=0, where h=0h=0, so applying hh again gives zero. When a=b=0a=b=0 the product is zero directly. These are planar instances of Lemma 3.3, Lemma 4.1 and Lemma 4.2.

The obstruction at two hidden layers. The case q=2q=2 and K=2K=2 illustrates the invariant. Vary four inputs and set the others to zero; there is at least one other input, since n≥qK+1=5n\ge q^K+1=5, so the target is max⁡(0,y1,y2,y3,y4)\max(0,y_1,y_2,y_3,y_4). For a bias-free integer-weight network, apply the cone product four times to the unit four-dimensional cycle. The ReLU of a single linear form has zero repeated product after two applications.

Locality of rectification, explained below, and commutation of the cone product then force the fourth product of every second-layer activation, and of their integer-weighted output, to be even. The fourth product of the target is one. This is the known obstruction for integer weights [16], here phrased through cone products.

The proof must construct its integer quotients and track integer coordinates through the cone operations; divisibility alone does not supply those finite witnesses. The full identities are proved in Lemma 3.3, Lemma 4.1, Lemma 4.2 and Lemma 5.1.

For odd-denominator rational weights, clearing denominators scales the target by an odd integer, so its fourth product stays odd. Bias domination, which scales the test points until the bounded change caused by deleting the biases cannot matter, and five agreement probes per chamber, one more than the four varied inputs (both under the next heading), then turn the obstruction into a disagreement for the original network. For general q,Kq,K, prime-power binomial identities replace this parity calculation, and the construction must supply every quotient, integer coordinate and test point inside the arithmetic theory. From the geometric obstruction to a refuter. We first reduce the rational candidate to a bias-free integer network in the fixed dimension d=qKd=q^K. A positive common denominator clears the nonbias weights, and deleting biases changes the original network by a computable uniform additive bound. The target becomes max⁡(0,x1,…,xd)\max(0,x_1,\ldots,x_d) after fixing the remaining inputs to zero.

We encode the relevant geometry by a finite arrangement of integer hyperplanes. Its cones have rational representatives obtained by a fixed number of perturbations of determinant-defined rays. Since dd is fixed, all representatives can be enumerated in polynomial time in the arrangement length. The enumeration has a completeness proof using bounded basis scans and two-dimensional sector calculations. This supplies actual finite data, rather than an appeal to an unspecified cell decomposition.

On these cones, a continuous piecewise-linear function supplies compatible chamber gradients. A cone product lowers dimension by one. We prove balance, commutation and invariance under refinement by explicit coordinate identities, following the intersection construction of Allermann and Rau [3]. A family with integer gradients need not give integer weights on every intermediate rational cone. Instead we maintain an integer twin: the product of a cone weight and its chosen exterior orientation has specified integer coordinates. At the final zero-dimensional cone the orientation is one, so the product value is an actual integer. This is the integrality needed by the modular contradiction.

The network-specific identity is locality of rectification. Writing H=max⁡(F,0)H = \max(F,0) for an activation family, HCHC for the cone product H⊙CH \odot C, and powers for repeated cone products, it gives

References

  1. [1][ABMM18] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding Deep Neural Networks with Rectified Linear Units. In International Conference on Learning Representations (ICLR), 2018. Full version arXiv:1611.01491v6, 28 February 2018.arxiv.org/abs/1611.01491
  2. [2][AHM25] G. Averkov, C. Hoiny, and M. Merkert. On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth. In International Conference on Learning Representations (ICLR), 2025. arXiv:2502.06283v2, 15 February 2025.arxiv.org/abs/2502.06283
  3. [3][AR10] L. Allermann and J. Rau. First Steps in Tropical Intersection Theory. Mathematische Zeitschrift, 264(3):633–670, 2010. Numbered citations refer to arXiv:0709.3705v3.DOI
  4. [4][BBH+26] Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff. Better neural network expressivity: Subdividing the simplex. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 500–507, 2026. Full version arXiv:2505.14338v3.arxiv.org/abs/2505.14338
  5. [5][BHR+26] Florestan Brunck, Christoph Hertrich, Kilian Rueß, Jack Stade, and Amir Yehudayoff. Two ReLU layers is all you need, 2026. arXiv:2610.28587v1. Version 1, 20 October 2026.arxiv.org/abs/2610.28587
  6. [6][CDJ26] M. Carmosino, N. Dang, and T. Jackman. Constructive Separations from Gate Elimination, 2026. arXiv:2604.23958v1, 27 April 2026.arxiv.org/abs/2604.23958
  7. [7][CJSW24] L. Chen, C. Jin, R. Santhanam, and R. Williams. Constructive Separations and Their Consequences. TheoretICs, 3:1–41, 2024. Article 3. Conference version in FOCS 2021, pages 646–657.
  8. [8][CN06] Stephen Cook and Phuong Nguyen. Foundations of Proof Complexity: Bounded Arithmetic and Propositional Translations, 2006. Author draft dated October 9, 2006; numbering in citations to this entry refers to this draft.
  9. [9][CN10] S. Cook and P. Nguyen. Logical Foundations of Proof Complexity. Perspectives in Logic. Cambridge University Press, 2010. Author draft posted September 2, 2008 (title page dated September 3); all numbered citations refer to that September 2008 draft.DOI
  10. [10][DIP+25] Remi Desmartin, Omri Isac, Grant Passmore, Ekaterina Komendantskaya, Kathrin Stark, and Guy Katz. A certified proof checker for deep neural network verification in Imandra. In Yannick Forster and Chantal Keller, editors, 16th International Conference on Interactive Theorem Proving, volume 352 of Leibniz International Proceedings in Informatics, pages 1:1–21. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2405.10611
  11. [11][FGHS26] V. Froese, M. Grillo, C. Hertrich, and M. Stargalla. Parameterized Hardness of Zonotope Containment and Neural Network Verification. In International Conference on Learning Representations (ICLR), 2026. Full version arXiv:2509.22849v3, 3 September 2026; numbered citations refer to this full version.arxiv.org/abs/2509.22849
  12. [12][Fu25] Yaoying Fu. Toric Geometry of ReLU Neural Networks, 2025. arXiv:2509.05894v1. Version 1, 7 September 2025.arxiv.org/abs/2509.05894
  13. [13][GC25] S. Grosser and M. Carmosino. Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1341–1347, 2025. Full version Electronic Colloquium on Computational Complexity, Report TR25-045, revision 1, 2025.DOI
  14. [14][GGL+26] M. Garlik, S. Gryaznov, J. Lu, R. Santhanam, and I. Tzameret. Meta-Mathematics of Algebraic Complexity. In 41st Annual Symposium on Logic in Computer Science (LICS 2026), volume 380 of Leibniz International Proceedings in Informatics, pages 49:1–49:25. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2026.DOI
  15. [15][Gok26] Chandrasekhar Gokavarapu. Proof-carrying verification for ReLU networks via rational certificates, 2026. arXiv:2512.4339v2. Version 2, January 12, 2026.arxiv.org/abs/2512.24339
  16. [16][HHL23] C. Haase, C. Hertrich, and G. Loho. Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes. In International Conference on Learning Representations (ICLR), 2023. arXiv:2302.12553.arxiv.org/abs/2302.12553
  17. [17][IBZK22] Omri Isac, Clark Barrett, Min Zhang, and Guy Katz. Neural network verification with proof production. In Alberto Griggio and Neha Rungta, editors, Proceedings of the 22nd Conference on Formal Methods in Computer-Aided Design (FMCAD 2022), pages 38–48. TU Wien Academic Press, 2022.arxiv.org/abs/2206.00512
  18. [18][Jeř15] E. Jeřábek. Open Induction in a Bounded Arithmetic for TC⁰. Archive for Mathematical Logic, 54(3–4):359–394, 2015.DOI
  19. [19][Jeř22] E. Jeřábek. Iterated Multiplication in VTC⁰. Archive for Mathematical Logic, 61(5–6):705–767, 2022. Numbered citations refer to the author PDF dated 23 September 2021.
  20. [20][Kai11] Volker Kaibel. Basic Polyhedral Theory. In James J. Cochran, Louis Anthony Cox, Jr., Pinar Keshinocak, Jeffrey P. Kharoufeh, and J. Cole Smith, editors, Wiley Encyclopedia of Operations Research and Management Science. Wiley, 2011. Numbered citations refer to arXiv:1001.2161v1.arxiv.org/abs/1001.2161
  21. [21][LLR26] Jiawei Li, Yuhao Li, and Hanlin Ren. Finding bugs in short proofs: The metamathematics of resolution lower bounds. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 788–798, 2026.arxiv.org/abs/2411.15515
  22. [22][Myr26] Dimitrios Myrisiotis. A hand-checkable proof that two hidden ReLU layers compute the maximum of six numbers, 2026. arXiv:2610.04256v1. Version 1, 3 October 2026.arxiv.org/abs/2610.04256

Paper details

vlnc:W_m6avc8fu
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

Codex, Claude Code

View statement
Looking for related papers…
Contents