Tropical Circuits with Scalar Multiplication Gates

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Tropical Circuits with Scalar Multiplication Gates

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Tropical Circuits with Scalar Multiplication Gates Christoph Hertrich1 and Moritz Stargalla1 1

University of Technology Nuremberg

[email protected], [email protected]

July 14, 2026

arXiv:2607.11540v1 [cs.CC] 13 Jul 2026

Abstract We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement max, +, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.

Introduction

Tropical circuits [Juk23], also known as max-plus circuits, are a variant of classical arithmetic circuits that use maximum and addition gates instead of addition and multiplication gates. Besides fundamental interest in the power of different models of computation and their dependence on the set of allowed operations, a primary motivation to study tropical circuits is to prove lower bounds on pure dynamic programs. By definition, a pure dynamic program consists of a predefined sequence of max (or min) and plus operations only. One example is the Bellman-Ford algorithm. Since every pure dynamic program can be written as a tropical circuit, lower bounds on the latter imply lower bounds on the former. That way, it has for example been shown that every pure dynamic program for the minimum spanning tree problem needs exponentially many iterations [JS19]. Recently, tropical circuits received increased attention due to their close connection to neural networks. Variants of tropical circuits have been used in order to prove size upper bounds for neural networks with rectified linear unit (ReLU) activations [HS25; HKL26]. Such neural networks can be defined as a circuit in which each node (neuron) computes an affine function of the outputs of its predecessors composed with the ReLU function x 7→ max{0, x}. It is straightforward to verify that a ReLU network can exactly simulate every tropical circuit. However, ReLU networks are strictly more powerful than tropical circuits, as they can, for instance, solve the minimum spanning tree problem in polynomial size [FGK16; HS25]. The main reason for this distinction seems to be the ability of neural networks to implement subtraction via negative weights: the construction at hand basically implements a (max, +, −)-circuit. However, besides subtraction, there is a second feature that seemingly makes neural networks more powerful than tropical circuits: namely scalar multiplication with arbitrary real constants. This opens up the question of how much additional power this feature provides alone, without allowing subtraction. To study this question, we propose to augment the model of tropical circuits by scalar multiplication gates with positive constants, calling the resulting model scalar tropical circuits (STCs). Every STC computes a continuous piecewise linear (CPWL) function of the form c 7→ maxx∈P c⊤ x for a polytope P , which is the support function fP of the polytope P .

1.1

Our Contributions

In the following we first detail our contribution in the context of tropical circuit theory and afterwards discuss implications, particularly in the context of neural networks. Lower Bounds on the Size of STCs. The size of a regular tropical circuit is the number of max and plus gates. We also measure the size of an STC Φ, denoted as size(Φ), as the number of max and plus gates, not counting scalar multiplication gates. Furthermore, we use size+ (Φ) to count only plus gates. It is easy to see that there are functions that can be computed by STCs of smaller size than tropical circuits. For example, x 7→ nx for n ∈ N≥2 can be realized by an STC of size 0 with one scalar multiplication gate, whereas a normal tropical circuit would require Ω(log n) plus gates. However, for functions that have only 0-1 coefficients, that is, functions of the form maxa∈A a⊤ x with A ⊆ {0, 1}d , the situation is less clear. Such functions are precisely support functions of 0-1 polytopes, also called multilinear tropical polynomials. To transfer size lower bounds from tropical

circuits to STCs for a particular function, one must show that allowing arbitrary positive scalar multiplications cannot reduce the circuit size. Interestingly, while one could expect that non-integral constants are of little use for representing support functions of 0-1 polytopes, this intuition breaks for a closely related question on neural network depth instead of size: Even for representing the very simple maximum function max{x1 , . . . , xn }, which is the support function of the standard simplex, one needs log2 (n) hidden ReLU layers if one restricts to integer weights [HHL23]. However, when allowing fractional weights, this can be done with log3 (n) hidden layers [BBHSY26]. One motivation for us is the question whether a similar phenomenon can occur for size instead of depth. A systematic way to obtain lower bounds on STCs is via extension complexity. The extension complexity xc(P ) of a polytope P is the minimum number of facets of any polytope Q that linearly projects to P . Extension complexity is a frequently studied notion in combinatorial optimization as it quantifies the minimum number of inequalities required in any linear program optimizing over P . It follows from [HL24] that xc(P )/2 lower-bounds the size of any STC computing fP . In seminal work, Fiorini, Massar, Pokutta, Tiwary, and Wolf [FMPTW15] and Rothvoss [Rot17] showed that, for example, the TSP polytope and the matching polytope have exponential extension complexity, which implies that STCs optimizing over those polytopes must have exponential size, too. However, there are several polytopes with polynomial extension complexity for which there are still exponential lower bounds on tropical circuits computing their support function, e.g., the Birkhoff polytope [JS82] or the (un)directed spanning tree polytope [JS82; Juk15; JS19]. This leads to the following question: Are there polytopes with polynomial extension complexity that require STCs of exponential size? We answer this question in the affirmative by giving two examples of classes of such polytopes. The first example is the Birkhoff polytope PPERM , which is the convex hull of all characteristic vectors of perfect matchings of the complete bipartite graph Kn,n . The problem of evaluating the support function fPPERM is often called the assignment problem. Further, fPPERM is the tropical version of the permanent. Jerrum and Snir [JS82] proved that any tropical circuit computing fPPERM must have at least 2Ω(n) plus gates (in fact, they show that at least n(2n − 1) plus gates are necessary). We extend this result by showing that any STC computing fPPERM must have at least 2Ω(n) plus gates. Theorem 1.1. Let PPERM be the Birkhoff Polytope for Kn,n . Then every STC Φ computing fPPERM satisfies size+ (Φ) ∈ 2Ω(n) . In particular, this shows that the lower bound via extension complexity in [HL24] can be exponentially loose, because xc(PPERM ) ∈ O(n2 ) [FKPT13]. We prove a similar result for the directed spanning tree polytope PDST , which is the convex hull of all characteristic vectors of directed spanning trees with root n of the complete directed graph with n nodes. Again, this extends a result by Jerrum and Snir [JS82], who showed that any tropical circuit computing fPDST has at least 2Ω(n) plus gates (in fact, they show that at least (4/3)n n−1 plus gates are necessary). Theorem 1.2. Every STC Φ computing fPDST satisfies size+ (Φ) ∈ 2Ω(n) . Proof Techniques. In our proofs, we generalize a widely used lower bounding technique from arithmetic and tropical circuit complexity. There, one first proves a decomposition lemma: if a

target polynomial with many monomials can be computed by a circuit of small size, then it can be written as a (tropical) sum of a small number of (tropical) products of simpler polynomials. A lower bound is then obtained by showing that each such simple product can contain only few monomials of the target function, so many products are needed to generate all monomials of the target function. This general technique has been widely used, for example, in [Hya78; Val80; HY11; RY11; Juk15; JS19; Yeh19; Sri20; CDGM22; KN26; CFMSY26], also compare the discussions in [SY10; Juk16]. For multilinear homogeneous polynomials, the degree of the monomials in a polynomial was often (implicitly) used as a measure for how simple a polynomial is [SY10; Juk15; JS19]. The decomposition lemmas from tropical circuit complexity cannot be applied to STCs, because scalar multiplication gates can create non-integral monomials which correspond to non-integral vertices in the corresponding Newton polytopes. In contrast, tropical circuits always yield Newton polytopes with integral vertices. We therefore use the duality between support functions and polytopes to prove a more general, polytopal version of the decomposition step. Namely, if the support function of a polytopeQ can be computed by a small STC Φ, then Q can be written as Sk Q = conv A0 ∪ i=1 (Ai + Bi ) with k ≤ size(Φ), where the addition is Minkowski sum, and the polytopes A0 , A1 , . . . , Ak are simple with respect to a suitable measure. For the polytopes PPERM and PDST in Theorem 1.1 and Theorem 1.2, we apply this decomposition and show that a single simple Minkowski sum Ai +Bi can contain only a small fraction of the vertices of our target polytope. For this, a crucial step is to choose a suitable measure. For multilinear homogeneous polynomials, using the degree of a polynomial as a measure is often sufficient to prove strong lower bounds for arithmetic and tropical circuits. The polytopal analogue of this measure is the function P 7→ maxv∈V (P ) | supp(v)|, where V (P ) is the set of vertices of P . For STCs, this measure does not naturally give strong lower bounds and one has to find other suitable measures, which is a challenge in itself. We instead use measures tailored to each problem such that Ai being simple with respect to that measure forces the Minkowski sum Ai + Bi to contain only a small fraction of vertices of the target polytope. Compared to tropical circuits, this requires additional work, as the polytopes Ai and Bi are not restricted to have only integral vertices. To this end, we derive structural constraints on Minkowski sums Ai + Bi contained in the target polytope, such that combining these constraints with the fact that Ai must be simple with respect to the chosen measure implies a bound on the number of vertices that can lie in one such Minkowski sum. This implies that we need many such Minkowski sums, leading to lower bounds on circuit size. Implications on Dynamic Programs. In light of the original motivation to study tropical circuits [Juk15; JS19; Juk23], Theorem 1.1 and Theorem 1.2 imply that pure dynamic programs solving the respective problems still need exponentially many iterations even if you augment them with the ability to perform positive scalar multiplications. Implications on Neural Networks. Our results imply a novel exponential size separation between monotone and non-monotone neural networks. Before we explain this separation result in detail, we first introduce maxout networks as a generalization of ReLU networks that is mathematically cleaner to analyze. A rank-k maxout network is a neural network in which each neuron computes the maximum of k affine functions of the outputs of its predecessors, instead of just computing the maximum of zero with a single affine function as in ReLU networks. The size of a maxout network is the number of maxout neurons. For every fixed k ∈ N≥2 , every rank-k maxout network can be simulated via a ReLU network with a constant multiplicative size overhead. 4

A neural network is called monotone if it does not contain any negative weight [DV10]. As a result, a monotone (ReLU or maxout) neural network computes a convex and monotone function. If one instead allows negative weights on outgoing connections of input neurons, but nowhere else in the network, one still ensures convexity, even if monotonicity might be lost. Such architectures are known as input-convex neural networks (ICNNs) [AXK17]. Disallowing negative weights can be beneficial for a variety of reasons. From a practical viewpoint, enforced monotonicity or convexity are an effective way to incorporate prior knowledge into the network architecture and make the model more interpretable [ZL26]. ICNNs have gained quite some popularity in the machine learning community for such reasons [AXK17; CSZ19; MTOL20; HCTC21], even though their performance is often significantly worse than with unrestricted models [GMSG25]. From a theoretical viewpoint, monotone models provide a restricted setting in which lower bounds can be proven more easily compared to the unrestricted model [MR25; Val24; BBHRY25; HL24], similarly to what is often done for related models of computation like Boolean or arithmetic circuits [Val80; AB87; SY10]. Note that, while in the non-monotone case ReLU and maxout networks are essentially equivalent, not every monotone maxout network can be simulated by a monotone ReLU network [BBHRY25]. Therefore, proving lower bounds on monotone maxout networks is potentially stronger than proving the same bounds for monotone ReLU networks. In order to formalize complexity statements about monotone and general neural networks, Hertrich and Loho [HL24] define the neural network complexity nnc(P ) of a polytope P as the minimum size of a rank-2 maxout network computing the support function fP ; and the monotone neural network complexity mnnc(P ) as the minimum size of a rank-2 maxout ICNN computing fP . If P is contained in the nonnegative orthant, then they show that mnnc(P ) equals the minimum size of a monotone maxout network computing fP , justifying the name mnnc(P ) even though it is defined via the more general ICNN model. As for STCs, lower bounds on ICNNs can be proved via extension complexity. More precisely, Hertrich and Loho [HL24] show that xc(P ) ≤ 2 · mnnc(P ) for every polytope P . Combined with the result by Rothvoss [Rot17], this implies an exponential lower bound on mnnc(PM ) for the matching polytope PM . However, although fPM can be computed in polynomial time [Edm65], it is unknown whether it can be exactly computed by a neural network of polynomial size, compare the discussion in [HS25]. Overall, the following question has been open so far. Are there functions representable with polynomial size neural networks for which maxout ICNNs need exponential size? We answer this question in the affirmative. More precisely, we obtain the following as corollaries of Theorem 1.1 and Theorem 1.2. Corollary 1.3. Let PPERM be the Birkhoff Polytope for Kn,n . Then mnnc(PPERM ) ∈ 2Ω(n) . This again shows that the lower bound based on extension complexity [HL24] can be exponentially loose, since xc(PPERM ) ∈ O(n2 ). Corollary 1.4. Let PDST be the directed spanning tree polytope on n vertices. Then, it holds that nnc(PDST ) ∈ O(n3 ) and mnnc(PDST ) ∈ 2Ω(n) . This answers the above question and shows that maxout ICNNs must sometimes be exponentially larger than their unrestricted counterparts to express the same functions. We obtain the corollaries by showing that STCs can simulate bias-free monotone maxout networks 5

with small overhead and combining this with our lower bounds for STCs. The upper bound in Corollary 1.4 follows from tropicalizing a polynomial-size subtraction-free (+, ×, /)-circuit of [FGK16] computing the arithmetic version of the polynomial fPDST , which gives a polynomial-size (max, +, −)-circuit computing fPDST .

1.2

Further Related Work

Our lower bounds are closely related to the literature on tropical and monotone arithmetic circuits. For a survey on arithmetic circuit complexity, see [SY10]. [JS82] related the tropical circuit complexity of homogeneous multilinear polynomials to monotone arithmetic circuit complexity and proved exponential lower bounds for several polynomials corresponding to combinatorial optimization problems, including the tropical permanent, TSP, and the maximum weight directed spanning tree problem. Subsequent works used tropical circuits as a model for pure dynamic programming and proved lower bounds for various settings [Juk15; Juk16; JS19; Juk23; KN26]. Interestingly, while many of those lower bounds for tropical circuits are proved via the non-tropical counterparts, it is less meaningful to de-tropicalize scalar multiplication gates. The reason is that in the tropical world, ⊙α the “freshman’s dream” is true, that is, (x1 ⊕ x2 )⊙α = α max(x1 , x2 ) = max(αx1 , αx2 ) = x⊙α 1 ⊕ x2 for α ∈ R>0 , while there is no natural way to distribute exponents over several additions in the non-tropical world for (x1 + x2 )α . More generally, the effect of extending circuit models with additional operations has been studied, for instance, in the setting of adding subtraction or division to arithmetic (+, ×)-circuits [Val80; FGK16], subtraction to tropical (max, +)-circuits [Juk23], and negation to boolean (∨, ∧)-circuits [Raz85; AB87; Tar88]. Another line of work studies the expressivity of ReLU and maxout networks through the viewpoint of polyhedral and tropical geometry; see also the survey [HMST26]. ReLU networks can be described as tropical rational functions [ZNL18]. Every CPWL function can be exactly represented by a ReLU network [ABMM18], and it is a prominent open question if constant depth is sufficient [HBDS23; HHL23; AHM25; GHL25; BBHSY26]. In contrast, there are families of functions that require monotone networks and ICNNs of unbounded depth [Val24; BBHRY25]. Every convex CPWL function can be computed by a ReLU ICNN [CSZ19]. However, there are convex monotone CPWL functions such as max{x1 , . . . , xn } that cannot be computed or even be approximated by a monotone ReLU network [MR25; BBHRY25]. In contrast, every convex monotone CPWL function can be computed by a monotone maxout network. Furthermore, ICNNs sometimes require strictly more depth than their unrestricted counterparts [GMSG25; BBHRY25]. In terms of size, mnnc(P ) can be lower-bounded via xc(P ), as discussed earlier. In addition, nnc(P ) can be lower bounded by a stronger version of xc(P ), called virtual extension complexity vxc(P ), quantifying the minimum number of linear inequalities required to formulate fP as a difference of two linear programs [HL24]. The extension complexity was related to the size of arithmetic and tropical circuits in [HY23]. Our paper studies lower bounds on the required size of ReLU networks. Upper bounds on the required size of ReLU networks have been studied for the knapsack problem in [HS23], for maximum flows and maximum (undirected) spanning trees in [HS25], and for regular matroids in [HKL26]. In particular, the latter result gives a first example of polytopes Pn where the best known upper bound on vxc(Pn ) ∈ O(n3 ) is lower than the best known upper bound on xc(Pn ) ∈ O(n6 ).

1.3

Outlook

We initiate the study of tropical circuits with scalar multiplication gates and prove in two concrete cases that such gates do not significantly increase the power of standard tropical circuits. The natural next step would be to extend our results to more cases or even prove a generalization: are there any 0-1 polytopes for which STCs can be more efficient in terms of size than standard tropical circuits? One way towards resolving this question negatively would be to search for general conditions that allow to transfer lower bounds on tropical circuits to STCs. A particularly intriguing open case is that of undirected spanning trees. Even for ordinary tropical circuits, it took several decades until the exponential lower bound in the directed case by Jerrum and Snir [JS82] was extended to the undirected case by Jukna and Seiwert [JS19]. While we do not believe that polynomial-size STCs can compute the support function of the undirected spanning tree polytope, extending the lower bound by Jukna and Seiwert [JS19] to STCs seems difficult as their techniques seem to rely on combinatorial structure that does not necessarily persist when allowing scalar multiplications. In the context of neural networks, our results imply an exponential separation between general networks and their monotone / input-convex counterparts for one concrete example, namely directed spanning trees. In the context of bipartite perfect matchings, we also obtain an exponential lower bound on mnnc(PPERM ), but it remains unknown whether nnc(PPERM ) is polynomial. Closely related, Jukna [Juk23, Section 6.5, Problem 3] explicitly states the open problem whether there are polynomial-size (max, +, −)-circuits to compute fPPERM . This is similarly in spirit to the famous open question whether there are (non-tropical) polynomial-size arithmetic circuits to compute the permanent, equivalently, whether VP = VNP, but it is more reasonable to expect a polynomial upper bound in the tropical case. An indication for this is that the tropical permanent can be computed in polynomial time via the Hungarian method, while evaluating the non-tropical permanent is #P-complete. However, polynomial-time computability does not imply the existence of polynomial-size (max, +, −)-circuits or neural networks, compare [HS25], and it remains an open problem whether there exists a class of CPWL functions that is computable in polynomial time, but not representable with polynomial-size neural networks [HL24]. A candidate for such a function class is the class of support functions of the (non-bipartite) matching polytope, as it has exponential extension complexity [Rot17], but can still be evaluated in polynomial time [Edm65]. More generally, our first example of an exponential separation between mnnc and nnc opens up the broader mission to figure out whether this is a singular phenomenon or whether there are many functions for which monotone networks are significantly less powerful than non-monotone variants. In other words, what features make a function difficult to represent for monotone networks? In this paper we focus on a real model of computation and require exact representations over real numbers. Especially in the practice of neural networks, approximate representations are often sufficient. It would therefore be interesting to study size lower bounds for approximating support functions with STCs. Approximation lower bounds have been studied for tropical circuits in [JS20], and for maxout ICNNs from the extension-complexity viewpoint in [HL24]. Finally, while we prove exponential lower bounds for STCs, the constants in the exponents of our lower bounds are weaker than in the related lower bounds on tropical circuits. It would therefore be interesting to close this gap. More precisely, dropping polynomial factors, our lower bound for PPERM is asymptotically 2cn for c ≈ 0.918 compared to 2n in [JS82]; for PDST , our lower bound is (9/7)n compared to (4/3)n in [JS82].

CPWL Functions Support Function

x2 x2

Polytopes (0,1)

Duality

0 x1

max{0, x1 , x2 }

Newton Polytope

(0,0)

(1,0)

Figure 1: Illustration of the duality between a CPWL function and a polytope.

Preliminaries

Notation. We define N = {0, 1, . . . } as the set of natural numbers including zero. For n ∈ N≥1 , we write [n] := {1, . . . , n}. We denote the standard basis vectors of Rd by {e1 , . . . , ed }. For two sets P, Q ⊂ Rd , their Minkowski sum is P + Q = {p + q : p ∈ P, q ∈ Q}. For z ∈ Rd , we write supp(z) = {i ∈ [d] : zi ̸= 0}. For λ ∈ R>0 and P ⊆ Rd , the dilation of P by λ is λP := {λp : p ∈ P }. A function f : Rd → R is monotone if f (x) ≤ f (y) for all x, y ∈ Rd with x ≤ y component-wise. It is positively homogeneous if f (λx) = λf (x) for all λ ∈ R≥0 . Polyhedra and Extension Complexity. A polyhedron P is the intersection of finitely many closed halfspaces P = {x ∈ Rd : Ax ≤ b}. A face of P is either the empty set or the set of maximizers arg max{c⊤ x : x ∈ P } of a linear function over P . Faces of dimension zero are called vertices; faces of dimension dim(P ) − 1 are called facets. A polytope is a bounded polyhedron. By the Minkowski-Weyl theorem, P can be equivalently written as a convex hull of finitely many points. The inclusion-wise minimal set V with conv(V ) = P is the set of vertices V (P ) of P . The extension complexity xc(P ) of a polytope P is the minimum number of facets of a polytope, possibly in a higher-dimensional space, that affinely projects to P . Support Functions and Duality. For a polytope P ⊂ Rd , the support function of P is fP : Rd → R, c 7→ maxx∈P c⊤ x. Support functions are convex, continuous piecewise-linear (CPWL), and positively homogeneous. The support function fP is monotone if and only if P ⊂ Rd≥0 . Let F d d be the subset be the set of positively homogeneous convex CPWL functions from Rd to R, and let F+ of monotone functions in F d . There is a standard duality between F d and the set P d of polytopes in Rd . The map φ : P d → F d , P 7→ fP is a bijection satisfying φ(P + Q) = fP +Q = fP + fQ , φ(conv(P ∪ Q)) = fconv(P ∪Q) = max{fP , fQ }, and φ(λP ) = fλP = λfP for all P, Q ∈ P d and all λ ∈ R≥0 . The inverse map φ−1 : F d → P d maps a function f ∈ F d to the unique polytope whose support function is f . We call this polytope the Newton Polytope of f . Restricting φ gives d and the set P d of polytopes in Rd . See Figure 1 for an illustration. a bijection between F+ + ≥0 Maxout Networks. We use the definition of maxout networks from [HL24]. A rank-k maxout neural network, where k ≥ 2, is given by a directed acyclic graph (V, A). The d ≥ 1 nodes of in-degree zero are called input neurons; all other s ≥ 1 nodes are maxout neurons. We assume that among the maxout neurons there is a unique output neuron of out-degree zero. Each node v computes a function zv : Rd → R. The i-th input node computes zv (x) = xi . Each maxout neuron

max

(a) Tropical circuit of size 10.

max

(b) STC of size 6.

max

Figure 2: Circuits in (a) and (b) compute max(3x1 + 2x2 + x3 , x1 + 3x3 , 2x2 + 3x3 ). The numbers in the orange scalar gates are the scalars. The trace in (c) corresponds to the monomial 3x1 +2x2 +x3 . v computes the maximum of k affine functions of the outputs of its incoming neighbors δv− :   X i zv (x) = max  wuv zu (x) + biv  , i=1,...,k

u∈δv−

i ∈ R for i = 1, . . . , k are weights of the arc uv ∈ A and bi for i = 1, . . . , k are biases where wuv v of the node v ∈ V . Maxout networks contain ReLU activations as a special case. The size of a maxout network is the number of maxout neurons. A maxout network is monotone if all weights are nonnegative. It is input-convex if negative weights are allowed only on arcs leaving an input neuron. Monotone maxout networks compute monotone and convex CPWL functions; maxout ICNNs compute convex CPWL functions. For a polytope P , the neural network complexity nnc(P ) is the minimum size of any rank-2 maxout network computing fP . The monotone neural network d, complexity mnnc(P ) is the minimum size of a rank-2 maxout ICNN computing fP . If P ∈ P+ then this coincides with the minimum size of a monotone rank-2 maxout network computing fP , see Lemma 3.2 below.

Tropical Circuits and Tropical Polynomials. A tropical circuit Φ is a directed acyclic graph, where parallel arcs are allowed. Each node, also called a gate, is of one of the following types. A gate of in-degree zero is an input gate and holds either one of the variables x1 , . . . , xd or the constant 0. Every other gate has in-degree two and computes either the maximum or the sum of the values computed at its two predecessor gates. We assume that there is a unique output gate of out-degree zero. The function computed at the output gate is denoted by fΦ : Rd → R. The size of Φ is the number of non-input gates. See Figure 2a for an illustration. Every tropical circuit computes a tropical polynomial fΦ (x) = maxa∈A a⊤ x for some finite set A ⊆ Nd . Conversely, every function of this form can be computed by a tropical circuit. Thus, d whose Newton polytopes are of the form tropical circuits compute exactly those functions in F+ d ⊤ conv(A) with A ⊆ N finite. A term a x for a ∈ A is called a tropical monomial. The degree of a ∈ Nd is a1 + · · · + ad . A tropical polynomial is homogeneous if all its monomials have the same degree, and it is multilinear if all coefficient vectors of monomials lie in {0, 1}d . Scalar Tropical Circuits. A scalar tropical circuit (STC) Φ is a tropical circuit with one additional type of gate. A scalar gate has in-degree one, is associated with a scalar λ ∈ R>0 , and maps an input value z to λz. For an STC Φ, its size size(Φ) is the total number of max and + gates.

max

max (4, 4) (2, 4) (2, 2) (1, 2)

(1, 1)

(0, 1)

(1, 0)

(2, 2) (1, 2)

(0, 2)

(1, 1) (2, 1)

(1, 0)

(2, 1)

(1, 0)

(0, 1)

(4, 2)

(2, 1)

(1, 0)

(2, 0)

Figure 3: Polytopal interpretation of an STC. Below each gate v is the corresponding polytope Pv . Scalar gates are not counted in size(Φ). We also write size+ (Φ) for the number of + gates. See Figure 2b for an example. The duality between polytopes and support functions gives a useful geometric interpretation of STCs. For every gate v, let fv : Rd → R be the function computed at v. We associate with v a polytope Pv ⊂ Rd≥0 such that fv = fPv . If v is an input gate holding xi , then Pv = {ei }. If v is an input gate holding 0, then Pv = {0}. If v is a max gate with predecessor gates u, w then Pv = conv(Pu ∪ Pw ). If v is a + gate with predecessor gates u, w, then Pv = Pu + Pw . If v is a scalar gate with predecessor u and scalar λ ∈ R>0 , then Pv = λPu . We denote the polytope associated with the output gate by PΦ . Then, Φ computes the support function fPΦ . This interpretation is illustrated in Figure 3. d . Conversely, every function in F d can be computed It follows that STCs compute functions in F+ + d can be built from dilations of standard basis vectors by a STC: each vertex of a polytope in P+ and the zero vector using + gates, and the convex hull of these vertices can then be built using max gates. Thus, one can equivalently view an STC as a circuit whose input gates hold the sets {0}, {e1 }, . . . , {ed } and whose non-input gates compute binary Minkowski sums, binary convex hulls of unions, and dilations. We will switch between these views without further comment. This interpretation generalizes Minkowski circuits as defined by Jukna [Juk16], which underlie several lower bound results for (+, ×) arithmetic and tropical circuits; see also the discussion in [Juk16, p. 2065]. Related polytopal viewpoints have also been used in the study of ReLU and maxout networks, for example in [HBDS23; BCLS25].

A General Lower Bound Strategy

In this section, we will develop the necessary prerequisites that allow us to reduce the problem of finding lower bounds to a more combinatorial / polytopal problem. We will use the following two lemmas to transfer lower bounds for STCs to lower bounds for maxout ICNNs. Lemma 3.1 ([HBDS23, Proposition 2.3]). If a rank-k maxout network computes a positively homogeneous function f , then the same network without biases also computes f . Lemma 3.2 ([HL24, Proposition 3.2]). If a rank-k maxout ICNN computes a monotone function f , then there is a monotone maxout network of the same size that computes f . d the support function f is monotone and positively homogeneous. Therefore, For polytopes P ∈ P+ P a lower bound for bias-free monotone maxout networks implies the same lower bound for maxout ICNNs computing fP . It remains to connect monotone maxout networks to STCs.

1 w1v

1 w2v

1 w3v

2 w1v

2 w2v

2 w3v

+ S1 =

1 j=1 wjv zj

3 w1v

+ S2 =

3 w2v

2 j=1 wjv zj

3 w3v

+ S3 =

max

max{S1 , S2 }

zv = max{S1 , S2 , S3 }

3 j=1 wjv zj

Figure 4: A rank-3 maxout node with three inputs represented as an STC. Orange nodes are scalar gates, green nodes are sum gates, and blue nodes are max gates. Lemma 3.3. If a bias-free monotone rank-k maxout network of size s computes a function f : Rd → R, then there is an STC Φ with size(Φ) ≤ ks2 + ksd that computes the same function f . Proof. Fix a bias-free monotone rank-k maxout network of size s ≥ 1. Each maxout neuron P i z (x) with weights w i ≥ 0. For each of the computes an expression zv (x) = maxi=1,...,k u∈δv− wuv u uv k affine functions, we use scalar gates for the nonzero weights and |δv− | − 1 sum gates to add the weighted inputs. We then use k − 1 max gates to take the maximum of the k sums; see Figure 4. If some weight is zero, we omit the corresponding scalar gate. If all weights of an affine function are zero, it is represented by the constant-0 input gate. Since |δv− | ≤ d + s for every maxout neuron v, one maxout neuron contributes at most k(d + s − 1) sum gates and k − 1 max gates. Thus, size(Φ) ≤ s(k(d + s − 1) + (k − 1)) ≤ ks(d + s) = ks2 + ksd.

Traces of STCs. For tropical circuit lower bounds it is useful to look at the monomials generated by the circuit. In arithmetic circuit theory subcircuits that compute monomials are called parse trees [JS82] or traces [Juk16]. We use the term trace. A trace T of an STC Φ is a subgraph of the directed acyclic graph underlying Φ and is defined recursively from the output gate as follows. Every trace T contains the output gate. Let v be a gate that is already in T . If v is a max gate, then exactly one predecessor gate and the corresponding arc are included in T . If v is a + gate, then both predecessor gates and the corresponding two arcs are included in T ; if the two arcs have the same tail, both arcs are still part of the trace. If v is a scalar gate, then its predecessor gate and the corresponding arc are included in T . See Figure 2c and Figure 5d for examples. Each trace T has a monomial coefficient vector aT ∈ Rd≥0 . It is computed by the STC given by the trace T where every max gate computes the function of its unique predecessor. Equivalently, an input xi contributes ei , the constant input 0 contributes the zero vector, a scalar gate with scalar λ multiplies the vector by λ, and a + gate adds the vectors coming from its two incoming arcs. Lemma 3.4. Let T be the set of all traces of an STC Φ, and let aT be the monomial coefficient vector of a trace T . Then fΦ (x) = max a⊤ T x, T ∈T

PΦ = conv{aT : T ∈ T }.

d ⊤ Proof. Every trace T corresponds to an affine function a⊤ T x with aT x ≤ fΦ (x) for all x ∈ R , since ⊤ each max gate of Φ is replaced by only one of its inputs. Hence maxT ∈T aT x ≤ fΦ (x). Fix x ∈ Rd .

From the output gate to the inputs, choose at every max gate a predecessor gate with the maximum ⊤ value at x. This induces a trace Tx with fΦ (x) = a⊤ Tx x ≤ maxT ∈T aT x and proves equality. We next prove the decomposition lemma that we use in our lower-bound arguments. It is a tropical and polytopal analogue of the fact that a polynomial computed by a small arithmetic circuit can be written as a sum of a small number of products of “simpler” polynomials. This general technique has been widely used, for example, in [Hya78; Val80; HY11; RY11; Juk15; JS19; Yeh19; Sri20; CDGM22; KN26; CFMSY26], also compare the discussions in [SY10; Juk16]. d → R Measure. We call a function µ : P+ ≥0 a measure if µ({0}) ≤ 1, µ({ei }) ≤ 1 for all i ∈ [d], d and, for all A, B ∈ P+ and all λ ∈ R>0 ,

µ(λA) = µ(A),

µ(A + B) ≤ µ(A) + µ(B),

and

µ(conv(A ∪ B)) ≤ µ(A) + µ(B).

We use the convention µ(∅) = 0. Later, in Sections 4 and 5, we will use measures of the form P 7→ maxv∈V (P ) | supp(π(v))|, where π : Rd → Rm is a linear map. d → R Lemma 3.5 (Decomposition Lemma). Let r ≥ 1, let µ : P+ ≥0 be a measure, and let Φ be d . Then there are an an STC with size(Φ) = t computing the support function of a polytope Q ∈ P+ d integer k ≤ t and polytopes A0 , A1 , B1 , . . . , Ak , Bk ∈ P+ such that

Q = conv A0 ∪

k [

! (Ai + Bi )

i=1

where µ(A0 ) ≤ r and r < µ(Ai ) ≤ 2r for all i = 1, . . . , k. Proof. We use induction on t. For t = 0, the output is obtained from an input gate using only scalar gates. Hence Q is either {0} or a dilation of some {ei }. In both cases µ(Q) ≤ 1 ≤ r, so the statement holds with k = 0 and A0 = Q. Assume now t ≥ 1. If µ(Q) ≤ r, then the statement again holds with k = 0 and A0 = Q. Thus, assume µ(Q) > r. Starting at the output gate, we move backwards to the input gates by recursively choosing a predecessor gate of maximum measure as long as some predecessor gate has measure greater than r. Since all input gates have measure at most 1 ≤ r, this process stops at a max or + gate v with µ(Pv ) > r with predecessor gates u, w such that µ(Pu ) ≤ r and µ(Pw ) ≤ r. Since µ is a measure, r < µ(Pv ) ≤ µ(Pu ) + µ(Pw ) ≤ 2r. Note that v cannot be a scalar gate, as scalar gates do not change the measure. Let Φv be the circuit obtained from Φ by deleting the arcs entering v and treating v as an additional input gate carrying the variable xd+1 . Non-input gates and arcs that cannot reach the output gate after the removal of the arcs are deleted; see Figure 5b for an example. For every x ∈ Rd , we have fΦ (x) = fΦv (x, fv (x)), since after substituting xd+1 = fv (x), the value at v in Φv equals the value at v in Φ and all other gates in Φv compute the same values as in Φ. Let T be the set of traces of Φv . The monomial coefficient vector of a trace T ∈ T is (aT , cT ) ∈

Rd≥0 × R≥0 and the trace T computes the monomial a⊤ T x + cT xd+1 . By Lemma 3.4, we have fΦv (x, xd+1 ) = max(a⊤ T x + cT xd+1 ). T ∈T

Using fv = fPv and cT ≥ 0 it follows that fQ (x) = fΦ (x) = fΦv (x, fv (x)) = max a⊤ T x + cT fv (x) = T ∈T

max

c∈conv{aT +cT p: T ∈T , p∈Pv }

Thus

c⊤ x.

! Q = conv{aT + cT p : T ∈ T , p ∈ Pv } = conv

[

({aT } + cT Pv ) .

T ∈T

We now partition T into two parts. Let Tv be the set of traces that contain gate v, and let T−v := T \ Tv . If T ∈ T−v , then cT = 0. If T ∈ Tv , then cT > 0, since the trace contains a directed path from v to the output gate and along this path all scalar factors are positive, while + gates only add other coefficients. We have Q = conv(R ∪ S), where ! [ R := conv ({aT } + cT Pv ) T ∈Tv

and S := conv{aT : T ∈ T−v }. With cmin = minT ∈Tv cT > 0, we have ! ! [ [ ({aT } + cT Pv ) = cmin · Pv + conv ({aT } + (cT − cmin ) · Pv ) =: A∗ + B ∗ , R = conv T ∈Tv

T ∈Tv

d and µ(A∗ ) = µ(c with A∗ , B ∗ ∈ P+ min Pv ) = µ(Pv ) ∈ (r, 2r].

It remains to consider S. If T−v is empty, we keep S = ∅. Otherwise, let Φ−v be the circuit obtained from Φv by deleting the input gate v and all arcs leaving it, and then recursively modifying the remaining circuit as follows. Delete scalar gates with no input, delete + gates with fewer than two inputs, and contract max gates with only one input by replacing the arcs leaving the max gate by direct arcs from its unique predecessor to its successor gates and deleting the max gate; see Figure 5c for an illustration. These simplifications preserve exactly the traces of Φv that do not contain v, since a trace without v is not affected by the deletions, and contracting max gates with only one input does not change the monomial coefficient vector of any trace. Therefore the traces of Φ−v are in bijection with the traces in T−v , with the same monomial coefficient vectors. By Lemma 3.4, Φ−v computes the support function of S. Also, size(Φ−v ) ≤ t − 1. If S ̸= ∅, we apply the induction hypothesis to Φ−v . This gives an integer ℓ ≤ t − 1 and polytopes Sℓ d A0 , A1 , B1 , . . . , Aℓ , Bℓ ∈ P+ with S = conv A0 ∪ i=1 (Ai + Bi ) and µ(A0 ) ≤ r and r < µ(Ai ) ≤ 2r for all i = 1, . . . , ℓ. If S = ∅, we can use ℓ = 0 and A0 = ∅. Then, with Aℓ+1 := A∗ and Bℓ+1 := B ∗ , we obtain ! ℓ+1 [ Q = conv A0 ∪ (Ai + Bi ) i=1

with ℓ + 1 ≤ t. This completes the induction. 13

max

v +

max

(a) STC Φ.

max

(b) STC Φv .

max

(d) Trace T of Φv .

Figure 5: Illustration of circuits in the proof of Lemma 3.5. The STC Φ in (a) computes fQ for Q = conv{(5, 3, 0), (5, 2, 1), (2, 6, 0), (2, 5, 1), (2, 1, 0), (1, 2, 0), (2, 0, 1), (1, 1, 1)}. The gate v in (a) computes fPv for Pv = conv{(2, 1, 0), (1, 2, 0)}. The STC Φv in (b) computes fP for P = conv{(1, 1, 0, 2), (1, 0, 1, 2), (0, 2, 0, 2), (0, 1, 1, 2), (2, 1, 0, 0), (1, 2, 0, 0), (2, 0, 1, 0), (1, 1, 1, 0)}. The STC Φ−v in (c) computes fS for S = {(2, 1, 0), (1, 2, 0), (2, 0, 1), (1, 1, 1)}. The monomial coefficient vector of the trace T in (d) is (1, 0, 1, 2). In (b) and (c), greyed out gates and arcs are deleted; the new dashed arc comes from the deletion of the max gate. Lemma 3.5 can be used to prove lower bounds on the size of STCs. The idea is to choose a measure and then show that every decomposition of the form in the lemma requires many summands Ai +Bi . Additionally, if max gates do not increase the measure, then the same argument gives a lower bound on the number of + gates. d , and let µ : P d 7→ R Corollary 3.6. Let r ≥ 1, let Q ∈ P+ ≥0 be a measure. Suppose that for + d with µ(A ) ≤ r, r < µ(A ) ≤ 2r for all i = 1, . . . , k, every collection A0 , A1 , B1 , . . . , Ak , Bk ∈ P+ 0 i S and Q = conv A0 ∪ ki=1 (Ai + Bi ) , it holds that L ≤ k. Then every STC computing fQ satisfies d , then every STC L ≤ size(Φ). Moreover, if µ(conv(A ∪ B)) ≤ max(µ(A), µ(B)) for all A, B ∈ P+ computing fQ satisfies L ≤ size+ (Φ).

Proof. The lower bound L ≤ size(Φ) follows directly from Lemma 3.5. For the stronger statement, d . In the proof of Lemma 3.5, the assume that µ(conv(A ∪ B)) ≤ max(µ(A), µ(B)) for all A, B ∈ P+ selected gate v and its predecessor gates u, w satisfy µ(Pv ) > r, µ(Pu ) ≤ r, and µ(Pw ) ≤ r. Such a gate cannot be a max gate under the additional assumption and must therefore be a + gate. Thus each summand Ai + Bi in the decomposition comes from a distinct + gate, and the same argument gives L ≤ size+ (Φ). For homogeneous multilinear polynomials f with many monomials, variants of Corollary 3.6 using the degree as a measure have been (implicitly) used to prove lower bounds for arithmetic and tropical circuits [SY10; Juk15; JS19]. In our setting, this degree measure corresponds to A 7→ maxv∈V (A) | supp(v)|. A common strategy is to show that each summand Ai + Bi contains only few monomials, which then yields a lower bound on the number of summands Ai + Bi necessary to produce all monomials of f . Our proofs follow existing counting ideas from the lower bound proofs for arithmetic and tropical circuits in [SY10; Juk16; Juk23], but we have to account for fractional vertices and use different measures.

Lower Bounds for the Birkhoff Polytope

d is a pair of polytopes (X, Y ) with X, Y ∈ P d and Rectangles. A rectangle of a polytope P ∈ P+ + X +Y ⊆ P . A rectangle is nonempty if X +Y ̸= ∅. It is vertex-realizing if (X +Y )∩V (P ) ̸= ∅.

Let Mn ⊂ {0, 1}n×n be the set of characteristic vectors of perfect matchings of the complete bipartite graph Kn,n . Recall that a matching is a set of edges where no two edges share a common node. A matching M is perfect if every node is incident to exactly one edge in M . The Birkhoff Polytope is PPERM = conv(Mn ). It has the standard halfspace representation   n n   X X PPERM = z ∈ Rn×n : z = 1, i ∈ [n], z = 1, j ∈ [n] . ij ij ≥0   j=1

i=1

Our goal is now to bound the number of perfect matchings in a single rectangle X + Y ⊆ PPERM with n/3 < µ(X) ≤ 2n/3 for a suitable measure µ. P P For z ∈ Rn×n we define the node weights ai (z) := nj=1 zij and bj (z) := ni=1 zij . Lemma 4.1. Let (X, Y ) be a nonempty rectangle of PPERM . Then there are vectors a∗ , b∗ ∈ [0, 1]n such that, for all x ∈ X, ai (x) = a∗i

and

bj (x) = b∗j ,

i, j ∈ [n].

Consequently, for all y ∈ Y and i, j ∈ [n], we have ai (y) = 1 − a∗i and bj (y) = 1 − b∗j . Proof. Fix an arbitrary y ∈ Y . Then, since X + Y ⊆ PPERM , we have x + y ∈ PPERM and thus ai (x) = 1 − ai (y) =: a∗i for all x ∈ X and i ∈ [n]. Analogously, we obtain the statements for the node weights bj and for y ∈ Y . The next lemma shows that a rectangle induces a certain structure for the perfect matchings it contains. Lemma 4.2. Let (X, Y ) be a vertex-realizing rectangle of PPERM , let a∗ and b∗ be as in Lemma 4.1, and define I := {i ∈ [n] : a∗i > 0}, J := {j ∈ [n] : b∗j > 0}. Then, |I| = |J|, and every m ∈ (X + Y ) ∩ Mn satisfies supp(m) ⊆ (I × J) ∪ (I c × J c ). Proof. Let m ∈ (X + Y ) ∩ Mn and write m = x + y with x ∈ X, y ∈ Y . We have 0 ≤ x ≤ m and 0 ≤ y ≤ m. Since m is the characteristic vector of a perfect matching and x ≤ m holds, the edges in supp(x) form a matching mx in Kn,n . In particular, each node i ∈ I is incident to an edge in mx , and each node i ∈ / I is not incident to an edge in mx . The same applies to the nodes j ∈ J and j ∈ / J. Therefore |I| = |J| and supp(x) ⊆ I × J. Now consider an edge (i, j) ∈ supp(m). If (i, j) ∈ supp(x), then (i, j) ∈ I × J. If (i, j) ∈ / supp(x), then (i, j) ∈ supp(y), in which case i ∈ /I c c and the matching edge (i, j) must use a node j ∈ / J. Hence supp(m) ⊆ (I × J) ∪ (I × J ). In particular, if (X, Y ) is vertex-realizing, that is, (X + Y ) ∩ Mn ̸= ∅, then |(X + Y ) ∩ Mn | ≤ |I|! · (n − |I|)!.

We now choose a measure µM such that the restriction µM (X) ∈ (n/3, 2n/3] forces |I| to be bounded away from both 0 and n. Let P n×n µM : P+ → R≥0 , A 7→ maxa∈V (A) |{i ∈ [n] : nj=1 aij > 0}|. Again, for A = ∅, we use µM (∅) = 0. The measure µM corresponds to the degree-measure A 7→ maxv∈V (A) | supp(v)| after replacing | supp(v)| with | supp(π(v))| for a linear map π : Rn×n → Rn . n×n Proposition 4.3. The function µM is a measure. Moreover, for all A, B ∈ P+ ,

µM (conv(A ∪ B)) ≤ max(µM (A), µM (B)). Proof. We have µM ({0}) = 0 and µM ({eij }) = 1 for all i, j ∈ [n]. It is straightforward to show n×n that µM (c · A) = µM (A) and µM (A + B) ≤ µM (A) + µM (B) for all A, B ∈ P+ , c ∈ R>0 . Further, every vertex of conv(A ∪ B) is a vertex of A or a vertex of B. Thus µM (conv(A ∪ B)) ≤ max(µM (A), µM (B)). Lemma 4.4. Let (X, Y ) be a vertex-realizing rectangle of PPERM with µM (X) = r ∈ (n/3, 2n/3]. Then n! . |(X + Y ) ∩ Mn | ≤ n ⌊n/3⌋

Proof. By Lemma 4.1,

∗ ∗ j=1 xij = ai for all x ∈ X. With I = {i ∈ [n] : ai > 0}, we have

r = µM (X) = max |{i ∈ [n] : x∈V (X)

n X

xij > 0}| = max |{i ∈ [n] : a∗i > 0}| = |I|. x∈V (X)

j=1

By Lemma 4.2 and since r ranges over (n/3, 2n/3] ∩ N, we have |(X + Y ) ∩ Mn | ≤ r!(n − r)! =

n! n ≤ r

n ⌊n/3⌋

This allows us to state our lower bound for STCs computing PPERM . Theorem 1.1. Let PPERM be the Birkhoff Polytope for Kn,n . Then every STC Φ computing fPPERM satisfies size+ (Φ) ∈ 2Ω(n) . Proof. Consider a decomposition PPERM = conv A0 ∪

k [

! (Ai + Bi )

i=1

as in Corollary 3.6 with r = n/3, so µM (A0 ) ≤ n/3, n/3 < µM (Ai ) ≤ 2n/3 for all i = 1, . . . , k. Suppose that A0 ̸= ∅. Then, there is a v ∈ V (A0 ) ⊆ PPERM with µM ({v}) ≤ n/3, which contradicts the fact that µM ({x}) = n for all x ∈ PPERM . Thus we must have A0 = ∅.

Each of the n! perfect matchings must be contained in at least one rectangle. By Lemma 4.4 each perfect matchings. Thus rectangle contains at most n! n (⌊n/3⌋ ) n k≥ ∈ 2Ω(n) . ⌊n/3⌋ The lower bound on size+ (Φ) follows from Corollary 3.6 and Proposition 4.3. We obtain the following lower bound on mnnc(PPERM ). Corollary 1.3. Let PPERM be the Birkhoff Polytope for Kn,n . Then mnnc(PPERM ) ∈ 2Ω(n) . Proof. Let s be the size of a rank-2 maxout ICNN computing fPPERM . Since fPPERM is positively homogeneous and monotone, Lemma 3.1 and Lemma 3.2 imply that there is a bias-free monotone rank-2 maxout network of size s computing fPPERM . By Lemma 3.3 this gives an STC Φ with size(Φ) ≤ 2s2 + 2sn2 . By Theorem 1.1, size(Φ) ≥ 2Ω(n) . Thus 2s2 + 2sn2 ≥ 2Ω(n) , which implies s ≥ 2Ω(n) . Although one can optimize over PPERM in polynomial time, it is open whether there are (max, +, −)circuits or ReLU / maxout networks of polynomial size computing fPPERM ; see [Juk23, Section 6.5, Problem 3]. Thus, the lower bound above does not by itself separate mnnc from nnc. It does show, however, that the extension-complexity lower bound xc(P )/2 ≤ mnnc(P ) from [HL24] can be exponentially loose, because xc(PPERM ) = n2 for n ≥ 4 [FKPT13, Proposition 5.10]. Dropping polynomial factors, the 2Ω(n) lower bound from Theorem 1.1 is tight up to a multiplicative factor in the exponent. This was already observed by Jerrum and Snir [JS82]. Proposition 4.5 ([JS82, Section 4.3]). There is a tropical circuit of size O(n2n ) computing fPPERM . Proof. Jerrum and Snir [JS82] describe a (+, ×)-circuit of size O(n2n ) for computing the permanent. Tropicalizing this circuit, that is, replacing + gates by max gates and × gates by + gates, leads to the following dynamic program, which we sketch here for completeness. For I ⊆ [n] with |I| = |J|, let M (I) be the maximum weight of a matching that matches the first |I| nodes on the left to the nodes on the right in I. We have M (∅) = 0. For I ̸= ∅, we have with ℓ = |I| M (I) = max{M (I \ {i}) + xℓi }. i∈I

The output is M ([n]). We show that the recurrence is correct. Let M be a matching on the subgraph induced by [ℓ] × I of maximum weight W and let node ℓ on the left be matched to node v ∈ I on the right. Since W = (W − xℓv ) + xℓv = M (I \ {v}) + xℓv , we have W ≤ M (I). Moreover, each choice i ∈ I in the recursion corresponds to exactly one matching on [ℓ] × I, since M (I \ {i}) corresponds to a matching M ′ on [ℓ − 1] × I \ {i} and M ′ ∪ {(ℓ, i)} is a matching on [ℓ] × I. Thus W ≥ M (I), which proves equality and shows that the recurrence is correct. There are 2n subsets I ⊆ [n] and for each subset I, a total of |I| + operations and |I| − 1 max operations are performed. This gives a tropical circuit of size O(n2n ).

Lower Bounds for the Directed Spanning Tree Polytope

Let A = {(i, j) : i ∈ [n − 1], j ∈ [n] \ {i}} be the arc set of the complete directed graph where 2 only the node n has no outgoing arcs. Let An ⊂ {0, 1}(n−1) be the set of characteristic vectors of arborescences rooted at n. Here an arborescence, also called a directed spanning tree, is a set of arcs such that every node i ∈ [n − 1] has outdegree one and every vertex can reach node n. Equivalently, every nonempty subset S ⊆ [n − 1] has at least one outgoing arc leaving S. The directed spanning tree polytope is PDST = conv(An ) with the halfspace description     X X A zij ≤ |S| − 1, ∅ ̸= S ⊆ [n − 1] . zij = 1, i ∈ [n − 1], PDST = z ∈ R≥0 :   (i,j)∈A∩(S×S)

j∈[n]\{i}

The constraints

(i,j)∈A∩(S×S) zij are also called subtour-elimination constraints.

For z ∈ RA , we define the node weight of a node i ∈ [n − 1] by ai (z) := lemma is analogous to Lemma 4.1.

j∈[n]\{i} zij . The following

Lemma 5.1. Let (X, Y ) be a nonempty rectangle of PDST . Then there is a vector a∗ ∈ [0, 1]n−1 such that, for all x ∈ X, we have ai (x) = a∗i for all i ∈ [n − 1]. Consequently, for all y ∈ Y and i ∈ [n − 1], we have ai (y) = 1 − a∗i . The following lemma shows that the set of arcs that can appear in arborescences contained in a rectangle is restricted. Lemma 5.2. Let (X, Y ) be a vertex-realizing rectangle of PDST , and let a∗ be defined as in Lemma 5.1. Define I := {i ∈ [n − 1] : a∗i > 0}, J := [n − 1] \ I, and E := {(i, j) : mij = 1 for some m ∈ (X + Y ) ∩ An }. Then |E| ≤ (n − 1)2 − |I| · (n − 1 − |I|). Proof. We prove by contradiction that for every i ∈ I and j ∈ J, at most one of the arcs (i, j) and (j, i) belongs to E. Suppose that there are arborescences m, m′ ∈ (X + Y ) ∩ An with mij = 1 and m′ji = 1. We write m = x + y and m′ = x′ + y ′ with x, x′ ∈ X and y, y ′ ∈ Y . Since i ∈ I, we have P ∗ x ≤ m and m has exactly one outgoing arc from i, we must k∈[n]\{i} xik = ai > 0. Because 0 ≤ P have xij > 0. Since j ∈ J, we have k∈[n]\{j} x′jk = a∗j = 0, which implies x′ji = 0 (since x′ ≥ 0). ′ = x′ + y ′ = m′ = 1. Because X + Y ⊆ P ′ Hence yji DST , we have x + y ∈ PDST . However, it ji ji ji violates the subtour-elimination constraint for S = {i, j} ′ ′ ′ (x + y ′ )ij + (x + y ′ )ji = xij + yij + xji + yji ≥ xij + yji = xij + 1 > 1,

which gives a contradiction and proves the claim. Thus, at least |I||J| of the (n − 1)2 arcs in A are not in E, which gives |E| ≤ (n − 1)2 − |I| · |J| = (n − 1)2 − |I| · (n − 1 − |I|). We use the measure (n−1)2

µA : P+

→ R≥0 ,

A 7→ maxa∈V (A) |{i ∈ [n − 1] :

j∈[n]\{i} aij > 0}|

Proposition 5.3. The function µA is a measure. Moreover, for all A, B ∈ P+

µA (conv(A ∪ B)) ≤ max(µA (A), µA (B)). Proof. The proof is identical to the proof of Proposition 4.3. Lemma 5.4. Let (X, Y ) be a vertex-realizing rectangle of PDST with µA (X) ∈ ((n−1)/3, 2(n−1)/3]. Then n−1 7 |(X + Y ) ∩ An | ≤ (n − 1)n−1 . 9 P ∗ Proof. By Lemma 5.1, we have j∈[n]\{i} xij = ai for all x ∈ X and i ∈ [n − 1]. With I = ∗ {i ∈ [n − 1] : ai > 0}, we have r := µA (X) = |I|. Since r ∈ ((n − 1)/3, 2(n − 1)/3], we have r(n − 1 − r) ≥ 2(n−1) · (n−1) = 29 (n − 1)2 . With Lemma 5.2, it follows that 3 3 |E| ≤ (n − 1)2 − |I| · (n − 1 − |I|) = (n − 1)2 − r · (n − 1 − r) ≤ 97 (n − 1)2 . Every arborescence m ∈ (X + Y ) ∩ An is obtained by choosing exactly one outgoing arc for each node i ∈ [n − 1], and all chosen arcs must lie in E. Let di be the outdegree of node i in the directed graph induced by E. Then |(X + Y ) ∩ An | ≤

n−1 Y

Pn−1 di ≤

i=1

i=1 di n−1

!n−1

|E| n−1

n−1

n−1 7 ≤ (n − 1)n−1 . 9

Theorem 1.2. Every STC Φ computing fPDST satisfies size+ (Φ) ∈ 2Ω(n) . Proof. Consider a decomposition PDST = conv A0 ∪

k [

! (Ai + Bi )

i=1

as in Corollary 3.6 with r = (n − 1)/3. As in the proof of Theorem 1.1, we must have A0 = ∅. There are nn−2 arborescences and every arborescence contained in at least one rectangle. n−1must ben−1 By Lemma 5.4, one rectangle contains at most 97 (n − 1) arborescences. Therefore nn−2 = k≥ (7/9)n−1 (n − 1)n−1

n−1 n−1 9 1 1 · · 1+ ∈ 2Ω(n) . 7 n n−1

Again, the lower bound on size+ (Φ) follows from Corollary 3.6 and Proposition 5.3. Dropping polynomial factors, this lower bound is tight up to a multiplicative factor in the exponent. Proposition 5.5. There is a tropical circuit of size O(n2n ) computing fPDST . 19

Proof. We give an explicit dynamic program. For I ⊆ [n − 1], let D(I) be the maximum weight of an arborescence on the node set I ∪ {n} rooted at n. We set D(∅) = 0. For i ∈ [n − 1] and J ⊆ [n − 1] \ {i}, we define Mi (J) = max xik . k∈J∪{n}

Then, for I ̸= ∅, D(I) = max {D(I \ {i}) + Mi (I \ {i})} . i∈I

The output is D([n−1]). We now prove the correctness of the recurrence. For I = {i}, D({i}) = xin and the recurrence is correct. Now, let S be an arborescence on I ∪{n} (rooted at n) with maximum weight W and let v be a leaf of S with (v, w) ∈ S. Then, we have W = (W − xvw ) + xvw = D(I \ {v}) + Mv (I \ {v}) and thus W ≤ D(I). Every choice i ∈ I in the recurrence corresponds to an arborescence on I ∪ {n}, since D(I \ {i}) corresponds to an arborescence on I \ {i} ∪ {n} and Mi (I \ {i}) corresponds to choosing an arc from i to I \ {i} ∪ {n}. Thus D(I) ≤ W and equality follows. Hence the recurrence is correct. The values Mi (J) can be computed with max gates using O(n2n ) gates. The recurrence D(I) can be implemented with additional O(n2n ) + and max gates. Thus the total size of the induced tropical circuit is O(n2n ). For the upper bound in Corollary 1.4, we use a (max, +, −)-circuit which is the tropicalization of the (+, ×, /)-circuit that corresponds to the directed star-mesh transformation [FGK16]; see also [HS25] for a tropicalization of the undirected version. Corollary 1.4. Let PDST be the directed spanning tree polytope on n vertices. Then, it holds that nnc(PDST ) ∈ O(n3 ) and mnnc(PDST ) ∈ 2Ω(n) . Proof. Lower bound. The lower bound follows exactly as in Corollary 1.3. Let s be the size of a rank-2 maxout ICNN computing fPDST . Since fPDST is positively homogeneous and monotone, Lemma 3.1 and Lemma 3.2 give a bias-free monotone rank-2 maxout network of size s computing fPDST . By Lemma 3.3, this network gives an STC Φ with size(Φ) ≤ 2s2 +2s(n−1)2 . By Theorem 1.2, size(Φ) ≥ 2Ω(n) . Therefore 2s2 + 2s(n − 1)2 ≥ 2Ω(n) , which implies s ≥ 2Ω(n) . UpperP bound.QThere is a (+, ×, /)-circuit of size O(n3 ) which computes the basis generating polynomial S∈An (i,j)∈S xij via the directed star-mesh transformation [FGK16, Section 7]. Replacing + gates by max gates, × gates by + gates, and / gates by − gates yields a (max, +, −)-circuit of size O(n3 ) that computes fPDST by tropicalization [HKL26, Proposition 4]. Since a (max, +, −)-circuit of size s directly translates to a maxout network of size s, we have nnc(PDST ) ∈ O(n3 ). For the sake of completeness, we provide a sketch of the corresponding dynamic program here. We (1) start with arc weights xij = xij for i ∈ [n − 1] and j ∈ [n] \ {i}. For k = 1, . . . , n − 1, assume that (k)

the weights xij are defined on the current vertex set {k, k + 1, . . . , n}. Let yk =

max i∈{k+1,...,n}

(k)

xki

be the maximum weight of any arc that goes out of the node k at step k. The idea is to delete one node from the current graph and to modify the arc weights of the remaining arcs such that the maximum weight of an arborescence rooted at n of this smaller graph is equal to the weight of the maximum arborescence rooted at n of the original graph. The arc weights are modified via the

recursion (k+1)

xij

(k) (k) (k) = max xij , xik + xkj − yk

for all distinct i, j ∈ {k + 1, . . . , n} with i ̸= n. The output is y1 + · · · + yn−1 .

References [AB87]

Noga Alon and Ravi B Boppana. “The monotone circuit complexity of Boolean functions”. In: Combinatorica 7.1 (1987), pp. 1–22. [ABMM18] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. “Understanding deep neural networks with rectified linear units”. In: International Conference on Learning Representations. 2018. [AHM25] Gennadiy Averkov, Christopher Hojny, and Maximilian Merkert. “On the expressiveness of rational ReLU neural networks with bounded depth”. In: International Conference on Learning Representations. 2025. [AXK17] Brandon Amos, Lei Xu, and J Zico Kolter. “Input convex neural networks”. In: International conference on machine learning. PMLR. 2017, pp. 146–155. [BBHRY25] Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, and Amir Yehudayoff. “On the depth of monotone ReLU neural networks and ICNNs”. In: arXiv preprint arXiv:2505.06169 (2025). [BBHSY26] 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. 2026, pp. 500–507. [BCLS25] Andrei Balakin, Shelby Cox, Georg Loho, and Bernd Sturmfels. “Maxout polytopes”. In: arXiv preprint arXiv:2509.21286 (2025). [CDGM22] Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, and Partha Mukhopadhyay. “Monotone complexity of spanning tree polynomial re-visited”. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Vol. 215. 2022, 39:1– 39:21. [CFMSY26] Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff. “Negations are powerful even in small depth”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing. 2026, pp. 2071–2082. [CSZ19] Yize Chen, Yuanyuan Shi, and Baosen Zhang. “Optimal control via neural networks: a convex approach”. In: International Conference on Learning Representations. 2019. [DV10] Hennie Daniels and Marina Velikova. “Monotone and partially monotone neural networks”. In: IEEE Transactions on Neural Networks 21.6 (2010), pp. 906–917. [Edm65] Jack Edmonds. “Paths, trees, and flowers”. In: Canadian Journal of Mathematics 17 (1965), pp. 449–467. [FGK16] Sergey Fomin, Dima Grigoriev, and Gleb Koshevoy. “Subtraction-free complexity, cluster transformations, and spanning trees”. In: Foundations of Computational Mathematics 16.1 (2016), pp. 1–31. [FKPT13] Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, and Dirk Oliver Theis. “Combinatorial bounds on nonnegative rank and extended formulations”. In: Discrete Mathematics 313.1 (2013), pp. 67–83. [FMPTW15] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf. “Exponential lower bounds for polytopes in combinatorial optimization”. In: J. ACM 62.2 (2015), 17:1–17:23. 21

[GHL25]

[GMSG25]

[HBDS23]

[HCTC21]

[HHL23]

[HKL26]

[HL24] [HMST26]

[HS23]

[HS25]

[HY11] [HY23] [Hya78]

[JS19] [JS20] [JS82] [Juk15] [Juk16]

Moritz Leo Grillo, Christoph Hertrich, and Georg Loho. “Depth-bounds for neural networks via the braid arrangement”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. Anne Gagneux, Mathurin Massias, Emmanuel Soubies, and Rémi Gribonval. “Convexity in ReLU neural networks: beyond ICNNs?” In: Journal of Mathematical Imaging and Vision 67.4 (2025), p. 40. Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. “Towards lower bounds on the depth of ReLU neural networks”. In: SIAM Journal on Discrete Mathematics 37.2 (2023), pp. 997–1029. Chin-Wei Huang, Ricky TQ Chen, Christos Tsirigotis, and Aaron Courville. “Convex potential flows: universal probability distributions with optimal transport and convex optimization”. In: International Conference on Learning Representations. 2021. Christian Haase, Christoph Hertrich, and Georg Loho. “Lower bounds on the depth of integral ReLU neural networks via Lattice polytopes”. In: International Conference on Learning Representations. 2023. Christoph Hertrich, Stefan Kober, and Georg Loho. “Arithmetic circuits and neural networks for regular matroids”. In: International Conference on Integer Programming and Combinatorial Optimization. Springer. 2026, pp. 394–409. Christoph Hertrich and Georg Loho. “Neural networks and (virtual) extended formulations”. In: arXiv preprint arXiv:2411.03006 (2024). Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay. “When deep learning meets polyhedral theory: A survey”. In: INFORMS Journal on Computing (2026). Christoph Hertrich and Martin Skutella. “Provably good solutions to the knapsack problem via neural networks of bounded size”. In: INFORMS Journal on Computing 35.5 (2023), pp. 1079–1097. Christoph Hertrich and Leon Sering. “ReLU neural networks of polynomial size for exact maximum flow computation”. In: Mathematical Programming 210.1 (2025), pp. 377–406. Pavel Hrubeš and Amir Yehudayoff. “Homogeneous formulas and symmetric polynomials”. In: Computational Complexity 20.3 (2011), pp. 559–578. Pavel Hrubeš and Amir Yehudayoff. “Shadows of newton polytopes”. In: Israel Journal of Mathematics 256.1 (2023), pp. 311–343. Laurent Hyafil. “On the parallel evaluation of multivariate polynomials”. In: Proceedings of the tenth Annual ACM symposium on Theory of computing. 1978, pp. 193– 195. Stasys Jukna and Hannes Seiwert. “Greedy can beat pure dynamic programming”. In: Information Processing Letters 142 (2019), pp. 90–95. Stasys Jukna and Hannes Seiwert. “Approximation limitations of pure dynamic programming”. In: SIAM Journal on Computing 49.1 (2020), pp. 170–205. Mark Jerrum and Marc Snir. “Some exact complexity results for straight-line computations over semirings”. In: J. ACM 29.3 (1982), pp. 874–897. Stasys Jukna. “Lower bounds for tropical circuits and dynamic programs”. In: Theory of Computing Systems 57.1 (2015), pp. 160–194. Stasys Jukna. “Tropical complexity, Sidon sets, and dynamic programming”. In: SIAM Journal on Discrete Mathematics 30.4 (2016), pp. 2064–2085.

[Juk23] [KN26]

[MR25]

[MTOL20]

[Raz85] [Rot17] [RY11]

[Sri20]

[SY10]

[Tar88] [Val24] [Val80] [Yeh19] [ZL26]

[ZNL18]

Stasys Jukna. “Tropical circuit complexity”. In: Limits of Pure Dynamic Programming/by Stasys Jukna.- (2023). Kacper Kluk and Jesper Nederlof. “Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width”. In: 53rd International Colloquium on Automata, Languages, and Programming. Vol. 374. LIPIcs. 2026, 130:1–130:23. Dan Mikulincer and Daniel Reichman. “Size and depth of monotone neural networks: interpolation and approximation”. In: IEEE Transactions on Neural Networks and Learning Systems 36.4 (2025), pp. 6314–6325. Ashok Makkuva, Amirhossein Taghvaei, Sewoong Oh, and Jason Lee. “Optimal transport mapping via input convex neural networks”. In: International Conference on Machine Learning. PMLR. 2020, pp. 6672–6681. Alexander Razborov. “Lower bounds on the monotone complexity of some Boolean function”. In: Soviet Math. Dokl. Vol. 31. 1985, pp. 354–357. Thomas Rothvoss. “The matching polytope has exponential extension complexity”. In: J. ACM 64.6 (2017), 41:1–41:19. Ran Raz and Amir Yehudayoff. “Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors”. In: Journal of Computer and System Sciences 77.1 (2011), pp. 167–190. Srikanth Srinivasan. “Strongly exponential separation between monotone VP and monotone VNP”. In: ACM Transactions on Computation Theory (TOCT) 12.4 (2020), pp. 1–12. Amir Shpilka and Amir Yehudayoff. “Arithmetic circuits: a survey of recent results and open questions”. In: Foundations and Trends® in Theoretical Computer Science 5.3-4 (2010), pp. 207–388. Éva Tardos. “The gap between monotone and non-monotone circuit complexity is exponential”. In: Combinatorica 8.1 (1988), pp. 141–142. Juan L Valerdi. “On minimal depth in neural networks”. In: arXiv preprint arXiv:2402.15315 (2024). LG Valiant. “Negation can be exponentially powerful”. In: Theoretical Computer Science 12.3 (1980), pp. 303–314. Amir Yehudayoff. “Separating monotone VP and VNP”. In: Proceedings of the 51st Annual ACM Symposium on Theory of Computing. 2019, pp. 425–429. Jakob Paul Zimmermann and Georg Loho. “Hidden monotonicity: Explaining deep neural networks via their DC decomposition”. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2026, pp. 24107–24117. Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. “Tropical geometry of deep neural networks”. In: International Conference on Machine Learning. PMLR. 2018, pp. 5824–5832.

Record · ID 363273 · SHA-256 8d95dc3982f421e1
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.