The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Authors: Moritz Stargalla
Christoph Hertrich
Daniel Reichman
Venue: NeurIPS 2025 poster ()
Keywords: ReLU Neural Networks
Linear Regions
Counting Complexity
Primary area: theory
TL;DR: We systematically collect and unify different notions of 'linear regions' of ReLU networks from the literature and study the computational complexity of counting them.

Abstract: An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and \#P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Moritz Stargalla
Christoph Hertrich
University of Technology Nuremberg moritz. str.tt.stargallauun..ee
University of Technology Nuremberg christoph..errtrchhuutee hwwtricheutt..ccommmm
Daniel Reichman
Worcester Polytechnic Institute
daniel cei.hhnn@mmaal.l................ com
Abstract
An established measure of the expressive power of given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.
Introduction
Neural networks with rectified linear unit (ReLU) activations are among the most common and fundamental models modern machine learning. The functions represented by ReLU networks are continuous and piecewise linear (CPWL), meaning that the input space can be partitioned into finitely many pieces on each of which the function affine. Such pieces are called linear regions. This leads to the following intuition: the more linear regions a neural network can produce, the more complex problems is capable of solving. Consequently, starting with Pascanu et al.) [204] Montúfar et al. [2014), the number of linear regions became a standard measure of the expressive power of a ReLU network. Substantial effort has been put into understanding this quantity, e.g., by deriving upper and lower bounds depending the network architecture or by developing algorithms to count it. More information can found the surveys Huchette al. 2023] Balestriero al. 2025).
Despite the significant interest in understanding the number of linear regions, surprisingly little is known about the most natural associated computational complexity question: Given neural network. what are the time and space requirements needed to determine how many regions it has? The main objective of our paper is make progress on this question by proving on the problem of counting linear regions.
-thooreticl results
However, before one can even talk about counting linear regions, one has properly define them. What sounds like simple exercise is actually non-trivial task. In the literature, there exists variety of non-equivalent definitions of what counts some authors define it via possible sets of active neurons, others define it solely based on the function represented by the neural network. Some authors require regions be full-dimensional, or connected.
linear region of a ReLU network. For example,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

or even convex, others do not. Inconsistencies between definitions have led to confusion and even minor flaws in previous work, as we explain Appendix A..4
1.1 Our Contributions
Definitions of linear regions. In order to raise awareness to the technical, but important and non- trivial inconsistencies regarding the definition of linear regions in neural networks, we identify six non-equivalent, commonly used definitions in Section 3 We diseuss how they relate to each other and provide a table demonstrating which authors used which definitions in previous work. We do not make a recommendation about what definition is the most reasonable one to use, as this depends on the context, but we encourage all authors of future papers to be aware of the subtlcties carried by the different options and to be explicit about which definition they use and why.
Complexity of counting regions in shallow networks. As for many questions regarding ReLU networks, makes sense first understand the most basic case with one hidden layer. In Section [
we prove that, regardless of which of the six definitions one uses, the seemingly simple question of deciding whether shallow network has more than one linear region can indeed be decided in polynomial time. However, for all six definitions, we show that determining the exact number of regions is #P-hard, meaning that, unless the commonly believed conjecture #P # FP fails, one cannot count regions of a shallow network in polynomial time. Furthermore, our reduction shows that even finding an algorithm that approximately counts the number of regions for one hidden layer might be intractable, it would resolve long-standing open questions in the context of counting cells of hyperplane arrangements [Linial| 1986].
Complexity of counting regions in networks with more than one hidden layer. Wang [202]] showed that deciding if a deep neural network has more than K regions is NP- iP-hard. In Section we improve upon Wang] [2022] in several aspects. While the hardness by Wang [002) only applies to networks with logarithmically growing depth (in the input dimension), we show that hardness can be proved for every constant number of hidden layers 2 2 and even in the case K 1, that is, for deciding if the network has more than one linear region. Our reduction also implies running- time lower bounds based on the exponential-time hypothesis. We furthermore show that, unless common complexity assumptions fail, one cannot even approximate the number of regions within an exponential factor in polynomial time.
Counting regions using polynomial space. While most of our results are concerned with lower bounds, in Section 6 we turn our attention towards proving an upper bound on the computational complexity of region counting. Wang (2022) proved" that for one definition of linear regions, the problem can be solved in exponential time. We show the stronger statement that for three of our definitions, polynomial space is sufficient.
that
Limitations. Our paper is of theoretical nature and we strive towards a thorough understanding of the problem of counting regions from computational complexity perspective, As such, we naturally do not optimize our algorithms and reductions for efficiency or practical use, in contrast to, e.g.,
Serra et al. [2018) and Cai et al. [2023]. Our hardness results are of worst-case nature. Consequently, although beyond the scope of our paper, it is conceivable that additional assumptions render the problem tractable. For example, it would be very interesting to devise algorithms for region counting on networks that have been trained using gradient descent, as there is evidence that such networks have fewer regions [Hanin and Rolnick 2019], which might allow faster algorithms. Not all of our results are valid for all of the six definitions we identify. We discuss the open problems resulting from this in the context of the respective sections. In our list of definitions in Section 3 and the corresponding Table D we tried to capture the most relevant previous works linear regions, but full literature review, like Huchette et al. (2023), beyond the scope of our paper.
1.2 Related work
Huchette et al. 2023 survey polyhedral methods for deep learning, also treating the study of linear regions in detail. To the best of our knowledge, the first bounds the number of regions in terms of the network architecture (c.g., number of neurons, network depth) were developed by Pascanu et al.
2014 and Montúfar et al. 2014). Subsequently, better bounds were established [Raghu et al. 2017
'The proof by Wang
2022 works for different definition than claimed in their paper; see Appendix A.4

---

Arora et al., 2018 Serra et al., 2018 Zanotti 2025a]. Arora et al. (0188 prove that every CPWL function can be represented by ReLO network.
Several works have developed algorithms for enumerating linear regions. Serra et al. 2018 and
Cai et al. [023] present mixed-integer programming based routines to count the number of regions Masden [2025] presents an algorithm to enumerate the full combinatorial structure of activation regions. As discussed above, Wang [2022] provides some initial results on the computational complexity of counting regions, which we strengthen significantly in this paper. Our reductions are related other decision problems on trained neural networks, e.g., verification (Katz al. 2017]. deciding injectivity or surjectivity (Froese et al.
22255 b] or deciding whether the Lipschitz constant Virmaux and Scaman 2018 Jordan and Dimakis
of ReLU network exceeds certain threshold
2020
Another line of research has studied the question of how construct ReL.U networks for functions with a certain number of regions [He et al. [020) Chen et al., 2022 Hertrich et al. 2023 Brandenburg
2025 Zanotti 2025b]. The number of regions of maxout networks was studied by Montúfan et al.
al.
[2022]. Note that all our hardness results hold for maxout networks, too, as maxout is
generalization of ReLU, Goujon et al. [2024] present bounds for general piecewise linear activation
functions. The average number of linear regions was studied, among others, by Hanin and Rolnick
2019), Tseran and Montúfar (202T). Our work inspired by the aim better understand complexity- theoretic aspects of neural networks; another well-studied question in that regime is the complexity of
training [Goel al. 2021
Froese et al. 2022.
Froese and Hertrich 2023 Bertschinger et al. 2023
2 Preliminaries
For N. we write [n] := {1, [I....,n., n). For set P I", we denote by P. po, and OP its closure, interior, and boundary, respectively. The ReLU function is the real function x + max(0, x).. For any n N, we denote by IR" - R" the function that computes the ReLU function in each component.
Polyhedra, CPWL functions, and hyperplane arrangements. A polyhedron P is the intersection of finitely many closed halfspaces. A polytope is a bounded polyhedron. A face of P is either the set of the form arg min(c x is finite collection of polyhedra such that 0 E P, P E P then all faces of P are in P, and P. P P, then P P' a face of P and p'. A function f IR" + continuous piecewise linear (CPWL), if there exists a polyhedral complex P such that the restriction of f to each full- cull-dimensional polyhedron P E an affine function. If this condition is satisfied, then and P are compatible. A hyperplane arrangement H. is a collection of hyperplanes in R", A cell of a hyperplane arrangement an inclusion maximal connected subset of IR" (UHen H). A hyperplane arrangement naturally induces an associated polyhedral complex with the cells being the maximal polyhedra of the complex.
empty
P) for some e R A polyhedral complex P
ReLU networks. A ReLU neural network N with d 2 0 hidden layers is defined by d 1 affine transformations T(); R=-1 + R"; + A + ((6) for E [d + 1]. We assume that no and 7d+11 = 1. The ReLU network N computes the CWPL function fN R" + R with
fN T(++1) o oooo
The matrices (1)) E R0:XX.-1 are called the weights and the vectors ((i) E RT are the biases of the i-th layer. We say the network has depth d + and size s(N):= Ei= n,. Equivalently, ReLU networks can also be represented as layered, directed, acyclic graphs where each dimension of each layer is represented by one vertex, called a nearon. Each neuron computes an affine transformation of the outputs of its predecessors, applies the ReLU function, and outputs the result. We denote the CPWL function mapping the network input to the output of neuron v by fN.. 1n R. If the reference to the ReLU network N is clear, we abbreviate fN." by fe-
Activation patterns. Given a ReLUU network N, a vector a E (),())(N) is called an activation pattern of N if there exists an input R such that when N receives x: as input, the i-th neuron in N has positive output (is active) if a; 1 and 0 if a; O. Given an activation pattern
{0, 1 1)o(N) the network collapses to an affine function f% R" > R, and each neuron outputs an affine function f : R R (f& f is the zero function if a, 0). Again, if the reference to the ReLU network N is clear, we abbreviate f&, by f.
3

---

Encoding size. We use (-) to denote the encoding size of numbers, matrices, or entire neural networks, where we assume that numbers are integers or rationals encoded in binary such that they take logarithmic space. More details can be found in Appendix A.1
Computational Complexity. We give informal overview over notions of computational complexity and refer to [Arora and Barak 2009] for further reading. A function f {0, 1 - {0, } in if is computable in polynomial time by a deterministic Turing machine, in NP if it is computable in polynomial time by non-deterministic Turing machine, and in RP if it is computable in polynomial time by randomized Turing machine that never outputs false positives and accepts correct input with probability at least 1/2. Intuitively. P contains problems that can be efficiently solved while NP contains those whose solutions can be efficiently verified. It widely believed that P NP and RP * NP hold. A function f {0, 1 + N is in #P if there is a polynomial time non-deterministic Turing machine, which has exactly (x) accepting paths for any input x E {0, 1)" and in FPSPACE if f is computable by deterministic Turing machine that uses polynomial space. A problem is called hard for NP (analogously, for #P) if all other problems in this class can be reduced to it in polynomial time, and complete if it is both hard and contained in the class itself.
3 Definitions of linear regions
In this section we extract the six most commonly used definitions of linear regions from the literature and discuss their relations alongside with important properties and subtleties. Table provides an overview which previous papers use which definitions.
The set of inputs that have the same activation pattern induce subset of IR" on which fN is affine.
Definition (Activation Region). Given network N and activation pattern {0, (3 with support I S [s)],, the set SN,a = {I E R" : f f (x) > 0 for all i E I, f (z) I for all & I} is an activation region of N. If the reference the ReLU network is clear, abbreviate SN, a by S.-
Activation regions can be open, closed, neither open nor closed, and full- or low-dimensional, see Figure T for some examples. The (disjoint) union of all activation regions is exactly RR In partieular, the number of activation regions equals the number of activation patterns. It is important to note that the term activation region is used ambiguously. For example, Hanin and Rolnick (019) use the to refer to only full-dimensiona activation regions.
Definition (Proper Activation Region). Given a ReLU network N, a proper activation region of N is filll-dimensiooal activation region of N.
While the previous two definitions depend on the neural network representation itself, the following four definitions depend only the CPWL function represented by the ReLU network and are independent from the concrete representation.
Definition 3 (Convex Region). Given ReLU network and a polyhedral complex that is compatible with fN. a convex region of N given P is full-dimensional polyhedron P E P. The
Paper
Definitions
Paper
Definitions
Pascanu et al. 2014
Montúfar et al.
2022
Montúfar et al
2014
Wang 2022
Raghu et al.
2017
Cai et al. 2023
Arora et al.
2018
Hertrich cl al.
2023
Serra al.
2018
Huchette al
2023
Hanin and
Rolnick
2019
Goujon ct al.
2024
He et al.
2020
Brandenburg
al.
2025
Rolnick and Kording
2020
Masden
2025
Iseran and Montufar
202T
Zanotti
2025a
Chen et al. [022
Zanotti
2025b
Table 1: List of papers that
several definitions. Additional notes the papers marked
with an asterisk can be found in Appendix A.3 between Definitions and []
Lezeau et al. (2044) use another definition that lies
see Appendix A.4

---

2
-
Figure 1: ReLU network computing the function f f(x,)) y) = max(- min(0, (0)000)))),) -x)). The closed connected regions (center left) and the activation regions (center right) are displayed. The slice {(x:, 0) : 2 0} contained the two closed connected regions with functions (red) and yy (blue). We have Ra Rs R4 3. R3 = 4. R2 5 and Ru 7. In anti-clockwise direction starting from the region with value O, the activation patterns are 0101 10, 000000, 001001, 101001, 100000, 110010 and 110110 (neurons are ordered from the upper left to the lower right).
number of convex regions of N is the minimum number of convex regions of any polyhedral complex PP that is compatible with fN-
Note that many different polyhedral complexes can attain this minimal number. Hence, in general, it not possible refer to polyhedron as 'convex region of N' without specifying an associated polyhedral complex.
Another option to define linear regions is use inclusion- maximall connected subsets on which the function computed by the ReLU network is affine, leading to the following definitions.
Definition (Open Connected Region). Given a ReLU network N, an open connected region of N an open, inclusion-wise maximal connected subset of R on which fN is affine.
Definition 5 (Closed Connected Region). Given ReLU network N, closed connected region N is a (closed) inclusion-wit wise maximal connected subset of RR" on which fN is affine.
The subtle difference the definition of open and closed connected regions has an important consequence: As Zanotti 2025a] showed, Pi P2 = 0P, n OP2 holds for any distinct open connected regions Pi, Ps. Interestingly, the same is not true for closed connected regions. This is due the fact that closed connected region can continue on oow-dimesiional slice of another closed connected region, which leads to a part of the boundary of one closed connected region to be contained in the interior of another closed connected region. Zanotti [2025a] Figure 1] gives neat example where low dimensional slice even connects two seemingly disconnected full-dimensional sets; another example can found Figure D Every open connected region the interior of the closure of union of some proper activation regions, see Lemma A.2 However, closed connected region is in general not the closure of a union of some activation regions (see Appendix C.I..
Hanin and Rolnick 2019 define the set of open connected regions as the connected components of the input space where the set of points on which the gradient of fN is discontinuous are removed. Alternatively, the set of open connected regions is equal to the unique set S with the minimum number of open connected subsets such that Uses 5 = I and /N restricted to any S E S is affine, see Lemma The same is not true for closed connected regions, since there can be multiple sets S with the minimal number of closed connected subsets such that Uses S = IR" and fN restricted to any S Se S affine. For example, in Figure [ in such minimal set S there is exactly one closed subset corresponding to the closed connected region with the constant zero function. There are multiple options to choose this subset, e.g. (-o0, 0) [0. oo) or ((-o0, 0) x [0, oo)) {(x, 0) x > 0}.
By dropping the requirement of being connected, we obtain the following definition.
Definition (Affine Region), Given a ReLU network N, an affine region of N is an inclusion-wit maximal subset of R." on which fN is affine.
For each definition, linear region S C R" of a ReLU network N can be associated with an affine function g IRm - R such that [N(x) = g(x) for all S. The affine function g is unique S full-dimensional. We say that the function g is computed or realized on S. If is the zero function, we call a zero region and nonzero region otherwise. The following theorem immediate from the defimitions.
5

---

2-
2
0
-V
1-2
Figure The function max(0, x)) max(0. (0.-)) -y)- max(0, -- y) + min(max --),, max(0. (0.g) y. 2)) 2 min(max(0, x 1), m0x 1)). We have Rs = 7, Rs 8, and R4 9.
Theorem 3.1. Given ReLU network N, let R1, R2...., , Rg denote the number of activation regions, proper activation regions, convex regions, open connected regions, closed connected regions and affine regions, respectively. Then: Rs S Rş S R4 R3 R2 R1.
The examples in Figures I and 2 show that each inequality in Theorem 3.1 can be strict. Zanotti 2025a showed R4 O((Re)*+) (+ He al. (020) showed R3 (R&).. Trivially, R3 S 2*(
Problem definitions for counting linear regions. In the remainder of the paper, we consider algorithmic problems arising from counting linear regions. Both decision problems (e.g., deciding if the number of regions is larger than a given threshold) or function problems (such as computing exactly or approximately the number of linear regions) are detailed below.
K-REGION- DEGGION-DECISION
DECISION
Input: A ReLU network N.
Question: Does N have strictly more than K linear regions (according to a specified definition)?
LINEAR REGION COUNTING
Input: ReLU network N.
Question: What is the number of linear regions of N (according to specified definition)?
4 Counting regions: one hidden layer
In this section, we derive our results for ReL.U networks with one hidden layer. Our first main result is that I-REGION-DECISIA can be solved in polynomial time for ReLU networks with one hidden layer. Detailed proofs of the statements in this section are given in Appendix B.1 Theorem 4.1. 1-REGION-DECISIN for networks with one hidden layer is in P for Definitions) 7 to
The idea of the proof is as follows. In a ReLU network with one hidden layer, each neuron corresponds hyperplane that divides the input space into two halfspaces. It is not guaranteed that each hyperplane also leads to discontinuity of the gradient of _N. since the functions of the neurons with the same hyperplane may add up to affine function. The proof of Theorem shows that detecting whether hyperplane of a neuron is canceled can be done in polynomial time. All hyperplanes of the network cancel if and only if the network computes affine function and has thus only one linear region according to Definitions to 6 For Definitions and I-REGION-DECISION trivial.
Froese et al. 2025b Lemma 15] give a result similar to Theorem They show that for network with one hidden layer without biases, computes the constant zero function, and otherwise find a point on which the network computes a nonzero value. In contrast, Theorem considerrr biases and nonzero affine functions.
determine in polynomial time whether the network
Turning to the problem of exactly counting the number of regions, we show the following theorem.
Theorem 4.2. LINEAR REGION COUNTING for ReLU networks with one hidden layer is #P-hard for Definitions 5 and o and #P-complete for Definitions
Proof sketch. Containment in #P is easy for Definitions and since activation pattern {0, 1 (N) of a ReLU network N is unique certificate for (proper) activation region, which can

---

be verified in polynomial time by computing the dimension of the set S., see Lemma modifications are necessary to show #P containment also for Definitions 3 and
A.5 More
To prove #P-hardness, we reduce from the problem of counting the number of cells of a hyperplane arrangement which is #P-complete, [[inial 1986). Starting from hyperplane arrangement H. in R", we carefully construct neural network whose linear regions exactly correspond to the cells of
the hyperplane arrangement. With proper technical adjustments, this works for all six definitions. C
Linial [986] proved the #P-completeness of counting the number of cells of hyperplane arrange- ment by reducing from the #C-oomllete problem of counting the number of acyclic orientations of graph. His reduction implies that LINEAR REGION COUNTING remains #P- even for networks
with one hidden layer where A = (I,.... ..). 1), 6(4) 0, 6(2) = 0, and A is the transpose of an incidence matrix of a directed graph.
is an open problem whether LINEAR REGION COUNTING #P for Definitions 5 and Notice that a single activation pattern does not suffice certificate, since proper activation regions with non-empty intersection can have the same affine function. For example, consider the function max(0, x) max(0, -y) max(0, x with zero regions (-o0, 0] x [0, 2o) and [0, oc) x (-20, Oj.
To the best of our knowledge, it is unknown whether there is a polynomial factor approximation algorithm for approximating the number of cells in a hyperplane arrangement. Thus, it is also an open problem whether LINEAR REGION COUNTING has polynomial factor approximation algorithm that runs in polynomial time.
5 Counting regions: going beyond one hidden layer
Here, we prove hardness results for ReLU networks with more than one hidden layer. Detailed proofs of the statements in this section are given in Appendix B..2 together with more detailed discussions providing additional intuition for some of the proofs.
5.1 Hardness of the decision version
From a result of Wang 2022
the following theorem follows immediately.
Theorem 5.1 [Wang. 2022 ) For any fixed constant K E K REGGGNNNDDCIIIO for ReLU networks of depth (oo n.) NP-hard according Definitions
In their reduction from 3-SAT, they construct a network computing a minimum of n + 1 terms. As known constructions for computing the minimum require depth O(log n), this leads hardness for counting regions of networks with depth Ollog n). With Theorem 5.2 we improve on the result by showing that the problem remains Na-dard even for networks with two hidden layers.
Theorem 5.2. For any fixed constants K, L E N21, 1, 1, 2 2, K-REGION-DECISION for ReLU networks with hidden layers NP-hard for Definitions to
As consequence, we even obtain hardness of the question whether there exists more than a single region. Proving this special case also the first step of proving Theorem 5.2 as captured by the following lemma for the special case K = 1 and L = 2.
Lemma 5.3. BEREGION-DECISION for ReLU networks with two hidden layers is NP-complete according Definitions to 6
Proof sketch. We reduce from SAT. Given a SAT formula ø, we carefully construct a neural network No with two hidden layers that has nonzero regions contained in e e-hypercubes around (0-1) points that satisfy o and is constantly zero anywhere else. In this way, if ő is unsatisfiable, then No computes the constant zero function and has exactly one linear region. more than one linear region (one zero region and at least one nonzero region).
satisfialle, then No. has strictly
Given a 3-SAT formula with m clauses, the network No from the reduction the proof of Lemma 5.3 has input dimension and width ((m), whereas the network that is created in the reduction of Theoree 5.2 has input dimension ((m) and width O(m m + K). We note that there an alternative Froese al. 2025b Theorem 18] show that the
way to prove the harhards of Lemma 5.3
7

---

problem of deciding whether or not network without biases with one hidden layer has a point which evaluates positive value NP-complete. By taking the maximum of the output of the network used in their reduction with the zero function, we obtain the NP-hardness of Lemma 5.3 However, our reduction offers new perspective on the difficulty of the problem. fact, the ideas used in our reduction are built upon in Section 5.2 to obtain results on the hardness of approximation of LINEAR REGION COUNTING. Moreover, our reduction has different properties, for example, all nonzero linear regions are bounded. This is not possible without biases, since then, all nonzero regions correspond to union polyhedral cones.
Theorem 5.2 can be proven using Lemma 5.3 in two steps. First, we can extend the hardness result of Lemma 5.3 from 1-REGION-DECISS K linear regions, and second, we can increase the number of hidden layers of the resulting network from to by adding I, additional hidden layers that compute the identity function.
to K- REGION-DECISIOE
by adding new function with
As corollary of Theorem 5.2. we obtain insights on the following decision problem.
L-NETWOR--EQUVVALENG
Input: Two ReLU networks N, ''' with hidden layers. Question: Do the networks N and N' compute the same function?
Two ReLU networks compute the same function if and only if the difference of the networks is the zero function. Since this difference can be computed by single ReLU network, we obtain the following.
Corollary 5.4. NETWORR--EQUVVLENEE is in P, and, for any fixed constant L-NETWORK- FOUTVALENCE is coNP-complete.
We also obtain the following runtime lower bound based on the Exponential Time Hypothesis
Corollary 5.5. For any fixed constants K, L E N, 2 2, K-REGION-DECISSON and LINEAR REGION COUNTING for Definitions 3 to for ReL.U networks with input dimension n and L hidden layers cannot be solved in 20(n) or 2 (N)) time unless the Exponential Time Hypothesis fails.
The 20(n) lower bound can be seen as another example of the curse of dimensionality in machine learning. As the input dimension grows, the problem quickly becomes intractable.
5.2 Hardness of exact and approximate counting
Here, we show that even approximating the number of linear region is hard for certain definitions. We prove two inapproximability results for different network architectures. For the first result, we use the proof ideas of Lemma 5.3 to show the following lemma.
Lemma 5.6. For any fixed constant L E L 3, there is a reduction from #SAT to LINEAR REGION COUNTING for networks with L hidden layers according to Definitions aadd 5
Proof sketch. Given SAT formula o, the network N₂ from the proof of Lemma has some nonzero linear regions contained in the s-hypercube around every satisfying (0-1) point of ø. In order to get control over the number of linear regions created per satisfying point, carefully need to modify the network N₂ such that every satisfying assignment of Φ creates the same number of nonzero linear regions. This yields simple formula relating the number of linear regions of the ReL.U network with the number of satisfying assignments of Φ. We achieve this by taking the minimum of the modified network with an appropriate function, which increases the number of hidden layers by one but does not change the width compared to Ng. The reduction can be extended to ReLU networks with L 2 3 hidden layers as before.
We note that Lemma 5.6 does not hold for Definition 6 since the constructed network has multiple closed connected regions with the same affine function. Lemma (5.6] shows that network having few regions does not necessarily imply that the regions of the network are "easy to count". On the contrary, shows that instances with relatively few regions can lead to #P-hard counting problems.
"The Exponential Time Hypothesis [Impagliazzo and Paturi 2001 states that 3-SAT on a variables cannot be solved in 20(n) time.
8

---

The reduction from #SAT implies that approximatiig LINEAR REGION COUNTING is intractable as well, in the following sense: We define an approximation algorithm achieving approximation ratio S 1 as an algorithm that is guaranteed to return, given a network N as input, a number that is at least/ / times the number of regions of N. In fact, even though Lemma holds for Definitions 5 it is sufficient to prove the inapproximability result also for Definitions] 3 and 6
Theorem 5.7. For any fixed constant I. E N, 2 3, it is NP-hard to approximate LINEAR REGION
COUNTING for Definitions 3 to within an approximation ratio larger than (2 + 1)- for networks with L hidden layers and input dimension
Proof. If a SAT formula has no satisfying assignment, the network produced by the reduction of Lemma [5.6 will have exactly 1 linear region according to Definitions 3 to 6 Otherwise, it will have at least 1 + 2" linear regions according to Definitions |o If it was possible to achieve an approximation ratio larger than (2n -)) in polynomial time we could decide if a SAT formula is satisfiable in polynomial time. This concludes the proof.
We note that very similar ideas also rule out a fully polynomial randomized approximation scheme (FPRAS) for approximating the number of linear regions. A FPRAS [Jerrum 2003) is a randomized polynomial-time (in the size of the input and 1/E) algorithm that returns a number T such that
Prob[(1- R < T < (1 + R] 2 3/4, where R is the number of regions of the network.
Theorem 5.7 can be easily adapted to show no FPRAS can exist for estimating the number of regions
of neural network unless RP
Theorem 5.7 does imply hardness of approximation for ReLU networks with two hidden layers. In the following, we show that approximation is indeed hard for networks with two hidden layers for Definitions 6o although with a weaker inapproximability factor than in Theorem 5.7
Theorem 5.8. Given ReLU network with two hidden layers and input dimension n. for every E E (0, 1) it ha-d to approximate LINEAR REGION COUNTING by a ratio larger than O0O(n' ')
for Definitions 3 6
Proof Sketch. Given a SAT formula o, the network No in the proof of Lemma 5.3 has exactly one linear region if is unsatisfiable and at least 2 linear regions if is satisfiable. We proceed by showing that for a ReLU network N with R linear regions, the network computing the function f(M); Rnn + R, f (x111..... Fin, Tk1, ..., zkn) = Σ fN Tin) has exactly R linear regions. In words, ((k) is simply the sum of k copies of IN each having as input disjoint set of variables. Applying this construction to No for appropriate values of gives the desired result. O
6 Counting regions using polynomial space
Due to the #P-hardness of LINEAR REGION COUNTING, we do not expect that efficient (polynomial time) algorithms for counting the number of linear regions exist. Wang [002 claimed that LINEAR REGION COUNTING for Definition 5 would be in EXPTIME. As stated in Appendix A.4 the algorithm actually works for Definition generally not a union of activation regions, it is still an open problem whether even an EXPTIME algorithm is possible for Definition Also for Definition 3 to the best of our knowledge, is not clear whether an EXPTIME algorithm exists, because there are infinitely many options to choose the underlying polyhedral complex. On the contrary, we show this section that for Definitions T and G the number of regions can be computed in polynomial space and therefore also in EXPTIM
4 insteed of Definition Since closed connected regions are
Theorem 6.1. LINEAR REGION COUNTING is in FPSPACE for Definitions
Ladd
is not hard to see that computing the number of activation regions and proper activation regions is possible in space that is polynomial in (N). Consider the following (informal) algorithm: Given
ReLU network N. iterate over all 22(N) vectors in {0. 1) {x(( and for each vector (0, 1) (N), compute the dimension of S, in time polynomial in (N) (see Lemma A.5) to determine if Sa is an activation region or a proper activation region, and increase counter by one if this is the case.
The algorithm may be probabilistic and return the correct answer with probability bounded away from 1/2.

---

Counting the number of affine regions is slightly more complicated, because naive approach enumerating all the activation patterns would need to keep track of all the affine coefficients already seen to avoid double-counting, which is infeasible in polynomial space. Instead, we iterate over all possible affine functions by enumerating all possible coefficient combinations that have an encoding size of less than polynomial upper bound, and check if there is a proper activation region on which the affine function realized. The running time of this algorithm exponential in the encoding size of the network, but it suffices to prove FPSPACE containment.
We describe how count regions in Algorithm 2 The comments in the algorithms refer to the lemmas that show that the computation in the respective line can be performed in polynomial space.
Algorithm 1 SEARCHAFFINEPIECE
Input: A ReLU network N and a vector (a)...., (n, b) E Qn+t1 Output: 1 if Σ 0:39 + b is function of an affine region of N, else O.
for E (0, 1}=(Ma do
2: if dim S. = n1 then
(Lemma A.5
3:
if i 0,2; b fN (z) then return return
(Lemma A.4
Algorithm 2 EXHAUSTIVESEARCH
Input: A ReLU network N. Output: Number of affine regions of N.
7max = max M1...., ld-1)
2: U U==236<<< 2a (Amax)
(Lemma A.3
3: R=0
4: for (a,b) E
Ujat1 x f1....,U)"" do
5: if ('god(as (i, bi) for E [1 then
3- 6: R R+ SEARCHAAFFINSPECCE (
An+1
(Lemma B.4
return R
The algorithms for counting (proper) activation regions (Definitions) T and 2 show fixed-paramete tractability of LINEAR REGION COUNTING with respect to the number of neurons. Furthermore, recent results of Froese et al. [2025a] Corollary 4.4] imply W[L]-hardness of LINEAR REGION COUNTING for ReLU networks with two or more hidden layers when parameterized by the input dimension (for Definitions 3 to 6). However, the exed-parrmettr tractability status of LINEAR REGION COUNTING remains open for other parameterizations and definitions.
Conclusion
We collected and discussed six commonly used non-equivalent definitions for linear regions of ReLU networks. We proved HP-hardness for counting the number of linear regions (for all six definitions) and NP-hardness for several associated decision problems (for most definitions). We further showed that for ReLU networks with two or more hidden layers, even approximating the number of linear regions is NP-hard (again, for most definitions). On the positive side, showed that for some definitions, linear regions can at least be counted in polynomial space.
There remain many interesting open problems and directions for future work. Is LINEAR REGION COUNTING EXPTIME for Definitions 3 and (are there even finite algorithms)? Can some of the results in Sections 4 to 6 be extended to all six definitions? For example, is LINEAR REGION COUNTING for ReLU networks with one hidden layer contained in #P also for Definitions and 6 Is the problem of approximating the number of linear regions also NP-hard for ReLU networks with one hidden layer? Finally, it would be interesting to study the fixed parammereeeer tractability of LINEAR REGION COUNTING under different parameterizations and definitions.
References
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations,
10

---

2018.
Sanjeev Arora and Boaz Barak. Computational Complexity: Modern Approach. Cambridge University Press, 2009.
Randall Balestriero, Ahmed Imtiaz Humayun, and Richard G Baraniuk. On the geometry of deep learning. NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 72(4), 2025.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is cR-compeete. Advances in Neural Information Processing Systems, 36, 2023.
Brandenburg, Moritz Leo Grillo, and Christoph Hertrich. Decomposition polyhedra of piecewise linear functions, In International Conference on Learning Representations, 2025.
Junyang Cai, Khai-Nguyen Nguyen Nishant Shrestha, Aidan Good, Ruisen Tu, Xin Yu, Shandian Zhe, and Thiago Serra. Getting away with more network pruning: From sparsity to geometry and linear regions. In International Conference Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 200-218 Springer, 2023.
Lian-Lin Chen, Harinath Garudadri, and Bhaskar D Rao. Improved bounds neural complexity for representing piecewise linear functions. Advances in Neural Information Processing Systems, 35, 2022.
Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marein Pilipczuk, Michal Pilipczuk, Saket Saurabh, Marek Cygan, Fedor V Fomin, et al. Lower bounds based on the exponential-tiin time hypothesis. Parameterized Algorithms,, pages 467-521, 2015.
Vincent Froese and Christoph Hertrich. Training neural networks is np-hard in fixed dimension. Advances in Neural Information Processing Systems, 36, 2023.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74, 2022.
Vincent Froese, Moritz Grillo, Christoph Hertrich, and Moritz Stargalla. Parameterized hardness of zonotope containment and neural network verification. arXiv preprint arXiv:2509.22845 2025a.
Vincent Froese, Moritz Grillo, and Martin Skutella. Complexity of injectivity and verification of relu neural networks (extended abstract). In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2188-2189, PMLR, 2025b.
Komei Fukuda. Polyhedral Computation. Department of Mathematics, Institute of Theoretical Computer Science ETH Zurich, Zurich, 2020-07-10. ISBN 978-3-907234-00-55 doi: 10.3929/ ethz-b-000426218. Educational Material.
Surbhi Goel, Adam Klivans, Pasin Manurangsi. and Daniel Reichman. Tight hardness results for training depth-2 relu networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 202/), pages 22-1. Schloss Lagstuhl-Leibmiiz-Zeetrum für Informatik, 2021.
Alexis Goujon, Arian Etemadi, and Michael Unser. On the number of regions of piecewise linear neural networks. J. Comput. Appl. Math., 441:Paper No. 11 115667, 22, 2024. ISSN 0377- 1778.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. Advances in Neural Information Processing Systems, 32, 2019.
Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng. Relu deep neural networks and linear finite elements. J. Comput. Math., 38(3):502-522 2020. ISSN 1991199999
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of relu neural networks. SIAM Journal on Discrete Mathematics, 37(2):997-1029, 2023.
11

---

Joey Huchette, Gonzalo Muñoz. Thiago Serra, and Calvin Tsay. When deep learning meets polyhedral theory: A survey, arXiv preprint arXiv:2305.0024// 2023.
Russell Impagliazzo and Ramamohan Paturi. On the complexity k-sat. Journal of Computer and System Sciences, 62(2):367-335, 2001.
Mark Jerrum. Counting, sampling and integrating: algorithms and complexity. Springer Science & Business Media, 2003.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Neural Information Processing Systems, 33, 2020.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: an efficient SMT solver for verifying deep neural networks. In Computer aided verification. Part I., volume 10426 of Lecture Notes Comput. Sci., pages 97-117. Springer, Cham, 2017. ISBN 978-3-319-63387-99
Paul Lezeau, Thomas Walker, Yueqi Cao, Shiv Bhatia, and Anthea Monod. Tropical expressivity of neural networks. arXiv preprint arXiv:2405.20174. 2024.
Nathan Linial. Hard enumeration problems in geometry and combinatorics. SIAM J. Algebraic Discrete Methods, 7(2):331-333 1986. ISSN 0196-5212.
Marissa Masden. Algorithmic determination of the combinatorial structure of the linear regions of relu neural networks. SIAM Journal on Applied Algebra and Geometry, 9()):774-444, 2025.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in Neural Information Processing Systems, 27, 2014.
Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. SIAM J. Appl. Algebra Geom., 6(4):618 649, 2022. ISSN 2470-6566.
Razvan Pascanu, Guido Montúfar, and Yoshua Bengio. On the number of inference regions of deep feed forward networks with piece-wise linear activations. In International Conference Learning Representations, 2014.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning. 2017.
David Rolnick and Konrad Kording, Reverse-engineeringg deep relu networks. In International Conference on Machine Learning, 2020.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting lincar regions of deep neural networks. In International Conference on Machine Learning, 2018.
Hanna Tseran and Guido F Montúfar. On the expected complexity of maxout networks. Advances in Neural Information Processing Systems, 34, 2021.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
Yuan Wang. Estimation and comparison of linear regions for relu networks. In Lud De Raedt, editor, Proceedings of the Thirty-Firs: International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3544-3550. International Joint Conferences on Artificial Intelligence Organization, 7 2022.
Main Track.
Leo Zanotti. Bounds on the number of pieces in continuous piecewise affine functions. arXiv preprint arXiv:2503.09525, 2025a.
Leo Zanotti. Lincar-size neural network representation of piecewise affine functions in IR? arXiv preprint arXiv:2503.13000 2025b.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We accurately describe our contributions in abstract and introduction. All claims are proven in the main text or appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We accurately discuss the limitations of our work in all appropriate places. We also have dedicated section about limitations at the end of Section [.]
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: All assumptions are mentioned in the statements. All proofs are given in the main text or appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ 'nipsscc/puullc//uuu http:///ggiddeeeoeouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps//neuripss.
Answer: [Yes]
Justification:
Purely theoretical research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Purely theoretical research.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Purely theoretical research.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No assets were used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No non-standard LLM usage.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
19


Reviews:
[{"review_id": "BdJ1nWPrAi", "reviewer": "Reviewer_gGKS", "summary": "The work studies the problem of counting linear regions expressed by ReLU networks, from the point of view of computational complexity. The paper provides worst-case complexity results for the decision problem of determining whether a ReLU net has $K>1$ regions, and the function problem of counting linear regions.\n\nThe authors identify non-equivalent notions of affine and activation regions in the literature and relate them. Then, they provide worst-case reductions for the decision and function problems considered, for shallow and deep MLPs.\n\nThe main results can be summarized as follows:\nFor shallow networks, the authors show that the decision problem can be solved in polynomial time, while the counting problem cannot.\nFor deeper networks, time-complexity bounds are provided establishing hardness of linear region counting. Importantly, the authors present hardness results even for approximate region counting and discuss some implications for “average-case” problem instances with randomized algorithms.\nFinally, improving upon prior work, the paper shows that for some notions of affine region, the function problem can be solved in polynomial space (and therefore in exponential time).", "questions": "I outline below a few technical questions that should be considered by the authors in order to broaden the impact of the work. I believe it is not necessary for the authors to fully address these questions in order for the paper to be accepted. However, I strongly encourage the authors to include a discussion of some of the points below in the next revision of the paper.\n\n1. Corollary 5.5 establishes an exponential relation between input space dimensionality and the hardness of region counting. Said dependency also appears in classical results on hyperplane arrangements – most notably Zaslavsky’s Theorem –  and is connected to the well known “curse of dimensionality” in ML. I think this relation should be discussed more explicitly by the authors. \n\n2. In the main text, it would be ideal to make explicit the dependency on $n_i$ and $L$ of Theorem 5.2, Lemma 5.3, and Theorem 5.7. Particularly, how does complexity scale as a function of $n_i$ vs $L$?\n\n3. Hanin and Rolnick (NeurIPS’19) argue that worst-case complexity solutions in the hypothesis space of ReLU nets under random Gaussian initialization are discrete points. I wonder if the worst-case solutions you construct in your proofs fall under the same category, or whether they are stable under small perturbations of the network’s parameters.\n\n4. I think it is of great value to draw connections between the complexity results presented in the paper and other problems in the literature that entail knowing the linear regions partition expressed by a ReLU network. A non-exhaustive list is:\n  * Estimating the Lipschitz constant of ReLU networks entails minimizing a quadratic form over the underlying polytopal complex (Virmaux and Scaman, 2018).\n  * Density estimation is related to the size of linear regions (Polianskii et al, 2022).\n  * Computing the spectral decay of a ReLU network (Rahaman, et al. 2019)\n\nOther minor points:\n\n* The labeling of R1, …, R6 in the caption of Figure 1 does not match the definitions given in Section 3. Indeed, the labeling used in the caption even contradicts Theorem 3.1. This is easily fixable.\n\n* It is common in Machine Learning literature to group hypotheses and assumptions in a dedicated paragraph, before stating technical results.  To further improve clarity and accessibility of the work, some assumptions and conjectures from computational complexity could be summarized in a dedicated section (e.g. in the appendix). It would be useful to include such a section (e.g. in the appendix) to recall common assumptions such as NP$\\ne$RP.\n\n### References\n\n* Complexity of linear regions in deep networks. Hanin and Rolnick. ICML 2019.\n* Deep relu networks have surprisingly few activation patterns. Hanin and Rolnick. NeurIPS 2019.\n* Lipschitz regularity of deep neural networks: analysis and efficient estimation. Virmaux and Scaman. NeurIPS 2018.\n* Voronoi density estimator for high-dimensional data: Computation, compactification and convergence. Polianskii et al. ICML 2022.\n* On the spectral bias of neural networks. Rahaman et al. ICML 2019.", "limitations": "Limitations of the work are properly discussed in Section 1.1. To further broaden the impact of the paper and improve contextualization of the findings in relation to the broader literature, I would have appreciated a closing discussion section describing how the technical results relate to other problems associated with linear region counting. A series of pointers is provided under “Questions” above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n1. The paper presents a nuanced discussion of worst-case computational complexity of linear region counting, under different non-equivalent notions of linear region.\n2. Reductions to known hard problems (SAT and cell-counting for oriented hyperplane arrangements) are presented formally and clearly.\n3. The work provides clear (counter-)examples illustrating the main technical nuances (main figures as well as appendix C). The gist of most proofs is included in the main paper.\n4. The paper shows that even approximate region counting is hard for MLPs, and touches upon hardness under randomized polynomial algorithms.\n\n## Weaknesses\n1. While it is very important to establish hardness results, worst-case problem instances are limited in that they don’t provide intuition on average-case hardness for certain problem distributions that are relevant in practice. Indeed, the hypothesis space of ReLU MLPs is very large and those worst-case solutions might be rare in practice. \n\n2. With the exception of Corollary 5.5, the dependency of the worst-case bounds on the depth and width of neural networks cannot be read directly from the main text, but only from the appendix. I believe such bounds are of independent interest beyond “region counting”, and so it would be useful to include them in the main paper.\n\n3. Other established works in the literature (Hanin and Rolnick, ICML’19 and NeurIPS’19), argue that, under certain assumptions, “worst-case complexity” instances are isolated (discrete) points in the hypothesis space of ReLU nets (see for instance Lemma 12 in Hanin and Rolnick, NeurIPS’19). It would be useful to relate the worst-case bounds to their results (see Questions below).\n\n4. The paper ends rather abruptly by sketching Algorithms 1 and 2. I think it is important to include a final discussion, relating the paper’s technical results with the broader literature (see Questions below). This was partially done under “Limitations”, in section 1.1.\n\n\n### Justification of the given scores\n\n**Quality:** The overall technical quality of the paper is high, with clear reductions to known hard problems. I particularly appreciate the discussion on computational hardness for randomized algorithms.\n\n**Clarity:** The paper is overall clear. Most concepts are clearly introduced in Section 2, making the paper accessible to interested but non-specialized readers. However, the dependency on input dimension, network width, and depth is sometimes not immediately clear from the main text, and can be found only in the appendix. This could be improved.\n\n**Significance:** The paper presents worst-case reductions for the decision and function formulations of linear region counting, for several notions of linear region as well as for shallow and deep MLPs. The work addresses some important technical inconsistencies within prior work, which are of interest beyond the narrower scope of the paper. \n\nMost importantly, the paper discusses the hardness of exact and approximate region counting. Since region discovery appears under different guises in the ML literature (from density estimation problems to estimating Lipschitz continuity and robustness), I believe the work provides a solid base on which further theoretical analysis can be made, for specific problem distributions.\n\n**Originality:** The work identifies a gap in the literature, whereby only limited technical results formally quantify hardness of region-counting problems (most notably Wang, 2022). The main technical novelty in terms of Mathematical proofs lies in constructing ReLU networks satisfying a given SAT condition, and then extending said construction to networks with depth $L > 1$. The proof technique was borrowed from Katz et al. (2017) as acknowledged by the authors.\n\nOverall, I appreciate the technical contributions advanced by the work, and the only limitations I see are with the paper’s broader impact beyond the “region counting” niche.", "was_revised": true, "final_justification": "I carefully read all reviews as well as the authors responses. I believe the paper provides a solid theoretical contribution, which is generally well presented and accessible.\n\nBefore the rebuttal, my main concern with this paper was whether it is too narrow to fit a major ML conference, with more theoretical conferences being more suited (e.g. COLT). This was also expressed by one other reviewer, who suggested borderline rejection. \n\nHowever, based on the two other reviews recommending acceptance, I decided to maintain my positive score.\n\nI strongly recommend the authors to address all raised points in the next revision of the paper, to make the message clearer and more accessible, and slightly broaden the impact of the work.", "rebuttal": "Thank you for carefully reading and evaluating our paper, and for your constructive feedback. We hope to have addressed all questions and comments in the responses below. If you have any further questions, please don’t hesitate to post them - we’ll be happy to clarify them.\n\n>1. While it is very important to establish hardness results, worst-case problem instances are limited in that they don’t provide intuition on average-case hardness for certain problem distributions that are relevant in practice. Indeed, the hypothesis space of ReLU MLPs is very large and those worst-case solutions might be rare in practice.\n\nWe fully agree. Our paper is only a first step in this regard and we will emphasize this point further. That said, worst-case analysis is a standard tool to understand the computational complexity of problems and is an important base case.\n\n>2. With the exception of Corollary 5.5, the dependency of the worst-case bounds on the depth and width of neural networks cannot be read directly from the main text, but only from the appendix. I believe such bounds are of independent interest beyond “region counting”, and so it would be useful to include them in the main paper.\n3. Other established works in the literature (Hanin and Rolnick, ICML’19 and NeurIPS’19), argue that, under certain assumptions, “worst-case complexity” instances are isolated (discrete) points in the hypothesis space of ReLU nets (see for instance Lemma 12 in Hanin and Rolnick, NeurIPS’19). It would be useful to relate the worst-case bounds to their results (see Questions below).\n\nWe answer these comments in the dedicated questions below.\n\n>4. The paper ends rather abruptly by sketching Algorithms 1 and 2. I think it is important to include a final discussion, relating the paper’s technical results with the broader literature (see Questions below). This was partially done under “Limitations”, in section 1.1.\n\nWe will add such a discussion in the revised version.\n\n>1. Corollary 5.5 establishes an exponential relation between input space dimensionality and the hardness of region counting. Said dependency also appears in classical results on hyperplane arrangements – most notably Zaslavsky’s Theorem – and is connected to the well known “curse of dimensionality” in ML. I think this relation should be discussed more explicitly by the authors.\n\nWe will discuss this point in the revised version.\n\n>2. In the main text, it would be ideal to make explicit the dependency on $n_i$ and $L$ of Theorem 5.2, Lemma 5.3, and Theorem 5.7. Particularly, how does complexity scale as a function of $n_i$ vs $L$?\n\nWe regret this was not clear. We will add a clarification of the dependencies in the main text. Restricting to 3SAT instances with $m$ clauses and $n\\leq 3m \\in \\mathcal{O}(m)$ variables, then, in Lemma 5.3, we construct networks with $L=2$, width $\\mathcal{O}(m)$, and input dimension $n$. The networks in Theorem 5.2 have $L$ hidden layers, width $\\mathcal{O}(m + K)$, and input dimension $n$. The networks in Theorem 5.7 have $L$ hidden layers, width $\\mathcal{O}(m)$, and input dimension $n$.\n\n>3. Hanin and Rolnick (NeurIPS’19) argue that worst-case complexity solutions in the hypothesis space of ReLU nets under random Gaussian initialization are discrete points. I wonder if the worst-case solutions you construct in your proofs fall under the same category, or whether they are stable under small perturbations of the network’s parameters.\n\nWe think that it is important to distinguish between worst-case instances in terms of computational complexity (“hard to count”) and those in terms of the linear region count (“many regions”). The relationship between these two notions is not straightforward - a network having few regions does not necessarily imply the regions of the network are “easy to count”. In fact, for Definitions 3 to 6, our reduction in Lemma 5.6 shows that instances with relatively few regions (compared to the worst-case number) can lead to #P-hard counting problems. While Hanin and Rolnick (NeurIPS 2019) reason about instances with “many regions” (for a generalization of Definition 2), our reductions construct instances that are worst-case instances in terms of computational complexity (“hard to count”), but these instances generally do not match the worst-case number of linear regions. In fact, counting regions can be seen as a method to identify whether an instance represents a worst-case in terms of linear region count.\nIt seems that the number of linear regions of the networks in our constructions is not stable under small perturbations of weights and biases for at least some of the six definitions, but making this rigorous is subject to further research.\n\n>4. I think it is of great value to draw connections between the complexity results presented in the paper and other problems in the literature that entail knowing the linear regions partition expressed by a ReLU network. A non-exhaustive list is:\n>- Estimating the Lipschitz constant of ReLU networks entails minimizing a quadratic form over the underlying polytopal complex (Virmaux and Scaman, 2018).\n>- Density estimation is related to the size of linear regions (Polianskii et al, 2022).\n>- Computing the spectral decay of a ReLU network (Rahaman, et al. 2019)\n\nWe will add a discussion on how our complexity results compare to results on other problems in the literature.\n\n>The labeling of R1, …, R6 in the caption of Figure 1 does not match the definitions given in Section 3. Indeed, the labeling used in the caption even contradicts Theorem 3.1. This is easily fixable.\n\nThank you for pointing this out! The ordering in the captions needs to be reversed. The caption for Figure 1 should read: $R_6 = R_5 = R_4 = 3, R_3 = 4, R_2 = 6$ and $R_1 = 8$. We will correct this in the camera-ready version.\n\n>It is common in Machine Learning literature to group hypotheses and assumptions in a dedicated paragraph, before stating technical results. To further improve clarity and accessibility of the work, some assumptions and conjectures from computational complexity could be summarized in a dedicated section (e.g. in the appendix). It would be useful to include such a section (e.g. in the appendix) to recall common assumptions such as NP$\\neq$ RP.\n\nWe will add a paragraph with hypotheses and assumptions and add explanations for complexity-theoretic assumptions."}, {"review_id": "y3CP66hcZe", "reviewer": "Reviewer_Bk2z", "summary": "This paper systematically investigates the computational complexity of counting linear regions in ReLU neural networks, a key measure of their expressive power. The authors first identify six non-equivalent definitions of linear regions used in literature, clarifying their relationships through a unified taxonomy. For shallow networks with only one hidden layer, they show that while detecting multiple regions is polynomial-time solvable, exact counting is #P-hard across all definitions. For deep networks, they significantly strengthen prior work by proving NP-hardness for any constant number of layers at least 2 and establishing strong inapproximability results. Notably, they demonstrate that even deciding whether a deep network has larger than 1 region is NP-complete. On the positive side, they prove polynomial-space upper bounds for three definitions. The work highlights fundamental limitations in analyzing neural networks through linear regions while providing rigorous complexity classifications. Key technical innovations include novel reductions from SAT/#SAT and careful handling of definitional subtleties that had caused inconsistencies in prior literature.", "questions": "1.Could the authors discuss whether their results imply limitations for empirical methods (e.g., sampling-based counting)? A brief discussion of practical workarounds (e.g., restricted network classes) would strengthen impact.\n\n2.The analysis is limited to ReLU networks. Do similar hardness results hold for smooth activations (e.g., sigmoid, GeLU)?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nQuality\n\n1.The paper is technically rigorous, with well-constructed proofs and reductions (e.g., #P-hardness for shallow networks, NP-hardness for deep networks).\n\n2.The authors carefully address inconsistencies in prior definitions of linear regions (Section 3, Table 1), which strengthens the theoretical foundation.\n\n3.The upper-bound result (Theorem 6.1, polynomial-space counting) is a meaningful contribution, showing that some variants of the problem are not as intractable as others.\n\nClarity\n\n1.The paper is well-structured, with clear distinctions between different definitions of linear regions and their implications.\n\n2.The writing is precise, though some proofs in the appendix are dense (as expected for a theoretical paper).\n\nSignificance\n\n1.The results have broad implications for understanding the expressive power and complexity of neural networks.\n\n2.The hardness results (Theorems 4.2, 5.2, 5.7-5.8) suggest fundamental limitations in analyzing ReLU networks via linear regions.\n\nOriginality\n\n1.The systematic comparison of six definitions of linear regions is novel and clarifies ambiguities in prior work.\n\nWeaknesses:\n\nQuality\n\n1.Some hardness results (e.g., Theorem 5.8) rely on somewhat artificial constructions (summing multiple copies of a network), which may limit practical implications.\n\n2.The paper does not explore whether certain restricted architectures (e.g., networks trained via gradient descent) might admit efficient counting algorithms, despite mentioning this as future work.\n\nClarity\n\n1.The distinction between Definitions 4 (open connected regions) and 5 (closed connected regions) could be explained more intuitively, as their differences are subtle.\n\n2.The proof sketches are helpful, but some steps (e.g., in Lemma 5.6) remain quite technical and may be hard to follow without careful reading.\n\nSignificance\n\n1.While the theoretical contributions are strong, the practical implications are less clear. The hardness results suggest that exact counting is infeasible, but do not explore whether heuristic or approximate methods (beyond worst-case analysis) could be useful in practice.\n\n2.The focus is purely on ReLU networks; extensions to other activation functions (e.g., sigmoid, GeLU) are not discussed.\n\nOriginality\n\n1.The paper builds heavily on prior work (e.g., Wang (2022), Hanin & Rolnick (2019)), and while it refines and extends these results, the core idea of studying the complexity of linear regions is not entirely new.\n\n2.The upper-bound result (Theorem 6.1) is somewhat incremental, as it mainly shows that some variants of the problem are in PSPACE rather than EXPTIME.", "was_revised": true, "final_justification": "After reading the rebuttal from the authors, and the discussions among other reviewers and authors, I tend to increase my score yet with unconfident evaluation. However, whether the task in this paper is suitable for NeurIPS is still an unresolved issue.", "rebuttal": "Thank you for carefully reading and evaluating our paper, and for your constructive feedback. We hope to have addressed all questions and comments in the responses below. If you have any further questions, please don’t hesitate to post them - we’ll be happy to clarify them.\n\n>1.Some hardness results (e.g., Theorem 5.8) rely on somewhat artificial constructions (summing multiple copies of a network), which may limit practical implications.\n\n>2.The paper does not explore whether certain restricted architectures (e.g., networks trained via gradient descent) might admit efficient counting algorithms, despite mentioning this as future work.\n\nWhile the theoretical focus and the constructions is indeed a limitation as we acknowledged, we still think that theoretical results like Theorem 5.8 represent a valuable contribution to NeurIPS. We agree that proving results for trained networks is very interesting. This itself presents a major challenge and we are not aware of previous hardness results for such trained networks. It could very well be a topic for a new paper on its own. In our view, before trying to prove results for special cases it seems essential to first prove worst case results, which is a standard tool to understand the computational complexity of problems and an important base case. Moreover, trained neural networks often have repeating structures, so maybe our constructions are not that unnatural after all.\n\n>1.The distinction between Definitions 4 (open connected regions) and 5 (closed connected regions) could be explained more intuitively, as their differences are subtle.\n\nWe acknowledge that the distinction between the two definitions is subtle and regret our explanation was not clear enough. Two main differences are that (1) closed connected regions can continue on low dimensional slices of the input space while open connected regions cannot; and (2) two open connected regions whose boundaries have a low-dimensional intersection ‘’merge’’ into a single closed connected region. These differences are illustrated in Figures 1 and 2. We will include additional details in the camera-ready version to explicitly highlight these two key differences.\n\n>2.The proof sketches are helpful, but some steps (e.g., in Lemma 5.6) remain quite technical and may be hard to follow without careful reading.\n\nWe acknowledge that some of the proofs are technically involved and may require careful reading to follow in full detail. While we consider this level of rigor as natural for a theoretical paper, we are happy to incorporate any concrete suggestions that could help make the proofs or proof sketches more accessible.\n\n>1.While the theoretical contributions are strong, the practical implications are less clear. The hardness results suggest that exact counting is infeasible, but do not explore whether heuristic or approximate methods (beyond worst-case analysis) could be useful in practice.\n\nTheorems 5.7 and 5.8 show that, for Definitions 3 to 6, approximating the number of linear regions for ReLU networks with two and more hidden layers within an exponential factor is NP-hard. We acknowledge that this does not fully resolve the question, as these results are of a worst-case nature, as explicitly noted in the paper. While average-case analyses and investigation of whether networks trained via gradient descent admit heuristic or approximation lie beyond the scope of this work, we view these directions as promising fields for further research.\n\n>2.The focus is purely on ReLU networks; extensions to other activation functions (e.g., sigmoid, GeLU) are not discussed.\n\nWe answer this in the dedicated question below.\n\n>1.The paper builds heavily on prior work (e.g., Wang (2022), Hanin & Rolnick (2019)), and while it refines and extends these results, the core idea of studying the complexity of linear regions is not entirely new.\n\nWe fully acknowledge that our work builds upon and is motivated by prior work. In our view, the fact that linear regions have been studied extensively in earlier work strengthens the relevance of our contributions, since our results represent a substantial advancement over prior work. We emphasize that we do not merely modify existing techniques used in prior work such as those by Wang [2022] or Hanin and Rolnick [2019], but introduce novel techniques and ideas. For example, in Algorithm 2, we present a method for counting affine regions in polynomial space by enumerating all possible coefficient combinations, thereby iterating over all possible affine functions implicitly without having to store them explicitly; and in Theorem 5.8, we use a new technique that amplifies inapproximability factors by summing multiple copies of a hard network.\n\n>2.The upper-bound result (Theorem 6.1) is somewhat incremental, as it mainly shows that some variants of the problem are in PSPACE rather than EXPTIME.\n\nPreviously, it was known that counting linear regions lies in EXPTIME for Definitions 1, 2 and Definition 4. While not being explicitly stated previously, devising an EXPTIME algorithm for Definition 6 is relatively straightforward. No further results were previously known, to the best of our knowledge. It remains open whether EXPTIME algorithms exist for Definitions 3 and 5. For Definition 4, PSPACE containment remains unclear. In contrast, PSPACE containment for Definitions 1 and 2 is relatively straightforward to establish, while Definition 6 requires new ideas, as outlined above. It also remains possible that PSPACE containment is the best achievable complexity bound for Definitions 1,2, and 6. Wang [2022] discusses the difficulty of proving that the problem is in NP for Definition 4, emphasizing that doing so would require fundamentally new ideas - a difficulty that seems to extend to all other definitions. Given this context, we think that our PSPACE result represents a meaningful advancement in the complexity-theoretic understanding of the problem.\n\n>1.Could the authors discuss whether their results imply limitations for empirical methods (e.g., sampling-based counting)? A brief discussion of practical workarounds (e.g., restricted network classes) would strengthen impact.\n\nTheorems 5.7 and 5.8 imply that for ReLU networks with 2 or more hidden layers, assuming NP $\\neq$ P, no polynomial-time algorithm can approximate the number of linear regions - for Definitions 3 to 6 - within a factor that is exponential in the input dimension. This implies that empirical methods would require a super-polynomial number of steps (in the encoding size of the network) to provide approximation guarantees for general instances. If the input dimension is fixed, however, polynomial approximation algorithms for Definitions 3 to 6 might exist. We note that our results do not rule out the existence of approximation algorithms for Definitions 1 and 2 - although, as noted in the paper, devising such an algorithm would resolve a longstanding open problem in combinatorics.\n\n>2.The analysis is limited to ReLU networks. Do similar hardness results hold for smooth activations (e.g., sigmoid, GeLU)?\n\nNote that the function computed by a network with smooth nonlinear activation functions (e.g. sigmoid, GeLU) is itself smooth. As a result, the concept of linear regions does not apply in this setting, since such functions generally do not partition the input space into finitely many regions where the function is affine linear. However, our results do extend to other continuous piecewise linear activation functions."}, {"review_id": "YmNVSnUHJV", "reviewer": "Reviewer_yJzi", "summary": "The paper considers fully-connected ReLU neural networks. It is well-known that the function associated to such a network is piece-wise linear. The paper studies the number of pieces (called linear regions) in the input space, where the function is linear. The paper provides 6 precise mathematical definitions of linear regions from the literature. Then, for these definitions, the paper provides results of a Theoretical-Computer-Science (TCS) nature on the computational complexity of counting the linear regions. There are positive and negative results.", "questions": "Can you exploit the extra page, if there is a camera ready step for the paper, to add \n- intuition about the Machine Learning impact of the results, especially on the differences between definitions\n- pedagogical explanations on the complexity theory concepts, for a general audience \n\nWhy is it written \"definitions X and Y\" instead of \"Definitions X and Y\" in the paper?", "limitations": "YES", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGTHS\nThe paper appears to be mathematically precise and rigorous. I agree with the authors that being mathematically precise about the definition and manipulation of a linear region is important, as without clarity, mistakes are quickly made, as the authors point out in the literature review. The results obtained by the authors appear to be wide, as they cover 6 existing definitions of linear regions, as well as several notions of complexity from TCS. I think studying theoretical properties of ReLU networks is important since they are fundamental in deep learning. \n\nWEAKNESSES The paper is a bit dry, probably because there are many results and because of the page limit. There does not seem to be machine learning intuition as to why different definitions lead to different computational complexities. The reading is not user-friendly to readers that are not experts in complexity theory, in my opinion.", "was_revised": true, "final_justification": "Given the author's response to me, and to the other reviews, I am quite confident in my positive evaluation of the paper, in the end.", "rebuttal": "Thank you for carefully reading and evaluating our paper, and for your constructive feedback. We hope to have addressed all questions and comments in the responses below. If you have any further questions, please don’t hesitate to post them - we’ll be happy to clarify them.\n\n>The paper is a bit dry, probably because there are many results and because of the page limit.\n\nWhile we strongly believe that rigor is essential in theoretical work, we regret that the paper has come across as somewhat dry.\n\n>There does not seem to be machine learning intuition as to why different definitions lead to different computational complexities. The reading is not user-friendly to readers that are not experts in complexity theory, in my opinion.\n\nWhile some of our results do not rule out the possibility that the true hardness of the studied problems is the same for all definitions (e.g. Theorem 4.2), the hardness changes depending on the definitions for other problems. For example, the problem of deciding if a ReLU network with two hidden layers has two or more regions is NP-complete for Definitions 3 to 6 (Lemma 5.3) but is trivial for Definitions 1 and 2. The corresponding intuition is that (proper) activation regions (Def. 1 and 2) seem to have a simpler structure than the other definitions. We will add explanations on complexity theory concepts in the camera-ready version of the paper.\n\n>Can you exploit the extra page, if there is a camera ready step for the paper, to add\n>- intuition about the Machine Learning impact of the results, especially on the differences between definitions\n>- pedagogical explanations on the complexity theory concepts, for a general audience\n\nWe will add additional intuition and explanations on complexity theory concepts for a general audience in the camera-ready version of the paper.\n\n>Why is it written \"definitions X and Y\" instead of \"Definitions X and Y\" in the paper?\n\nThank you very much for pointing this out! We will correct this in the camera-ready version of the paper."}, {"review_id": "KdlEHJLLhf", "reviewer": "Reviewer_sbxs", "summary": "This paper studies the computational complexity of counting the number of linear regions induced by ReLU neural networks. The authors identify and formalize six non-equivalent definitions of linear regions used in the literature. They prove that exact counting is #P-hard even for networks with one hidden layer, and that approximate counting is NP-hard for networks with two or more hidden layers. They also show that the decision problem (e.g., whether the number of regions exceeds a threshold) is NP-complete for networks with at least two hidden layers. Finally, they provide a positive result: exact counting is in FPSPACE for some of the definitions.", "questions": "1. Do the hardness results still hold in the absence of bias terms? It appears that the SAT-based reductions used in the paper rely on biases to construct bounded and localized nonzero regions. If the ReLU networks are restricted to be bias-free, do the same hardness results—particularly the NP-hardness and inapproximability for deep networks—still apply? Clarifying this would help understand whether the complexity arises inherently from the activation patterns or from representational power added by biases.\n2. Have the authors considered the parameterized complexity of counting linear regions? While the paper establishes strong worst-case hardness results (e.g., #P-hardness for 1-layer networks and ETH-based lower bounds in input dimension), it would be interesting to analyze whether the problem admits fixed-parameter tractable algorithms with respect to natural parameters such as the total number of neurons s(N), the network depth d, or the number of regions R.", "limitations": "1. The paper exclusively analyzes the worst-case computational complexity of counting linear regions. While this is important from a theoretical standpoint, it may not fully capture the behavior of ReLU networks encountered in practice—particularly those trained using gradient-based methods, which are often observed to induce relatively few linear regions.\n\n2. Although the authors show that region counting is in FPSPACE for some definitions, the algorithms presented are mainly of theoretical interest and not designed for practical implementation. There is little discussion of heuristics, approximations, or tractable special cases.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper offers a clear and systematic organization of existing literature by identifying and formalizing six non-equivalent definitions of linear regions, resolving ambiguities that have led to inconsistencies in prior work.\n2. It establishes new and strong computational hardness results, including #P-hardness for shallow networks and NP-/inapproximability results for deep networks under various definitions.\n\nWeaknesses:\n1. The results are based entirely on worst-case complexity analysis, which may not fully reflect the structure of practically trained networks. For instance, gradient-based training often induces fewer regions, potentially making counting easier in practice.\n2. The parameterized complexity of the problem is not explored; fixed-parameter tractability in terms of the number of neurons, depth, or region count remains an open direction.", "was_revised": true, "final_justification": "I appreciate the authors’ detailed rebuttal and clarifications. The paper makes a valuable contribution by formalizing multiple definitions of linear regions and establishing strong worst-case hardness results for counting them. The additional discussion on bias-free networks and parameterized complexity is helpful, though these directions remain largely open. My earlier concerns regarding the practical relevance of the results, given their focus on worst-case complexity, remain, but I agree that such results are an essential foundation before studying trained networks or special cases. Overall, the technical contributions are solid and well-presented, and I maintain my original score.", "rebuttal": "Thank you for carefully reading and evaluating our paper, and for your constructive feedback. We hope to have addressed all questions and comments in the responses below. If you have any further questions, please don’t hesitate to post them - we’ll be happy to clarify them.\n\n>1. The results are based entirely on worst-case complexity analysis, which may not fully reflect the structure of practically trained networks. For instance, gradient-based training often induces fewer regions, potentially making counting easier in practice.\n>2. The parameterized complexity of the problem is not explored; fixed-parameter tractability in terms of the number of neurons, depth, or region count remains an open direction.\n\nWe agree that proving results for trained networks is very interesting. This itself presents a major challenge and we are not aware of previous hardness results for such trained networks. In our view, before trying to prove results for special cases it seems essential to first prove worst-case results. We will explicitly mention the parameterized complexity question in the camera-ready version of the paper. We also think that it is important to distinguish between worst-case instances in terms of computational complexity (“hard to count”) and those in terms of the number of linear regions (“many regions”). The relationship between these two notions is not straightforward - a network having fewer regions does not necessarily imply the regions of the network are “easy to count”. In fact, for Definitions 3 to 6, our reduction in Lemma 5.6 shows that instances with relatively few regions (compared to the worst-case number of linear regions) can lead to #P-hard counting problems.\n\n>1.Do the hardness results still hold in the absence of bias terms? It appears that the SAT-based reductions used in the paper rely on biases to construct bounded and localized nonzero regions. If the ReLU networks are restricted to be bias-free, do the same hardness results—particularly the NP-hardness and inapproximability for deep networks—still apply? Clarifying this would help understand whether the complexity arises inherently from the activation patterns or from representational power added by biases.\n\nIt seems that our SAT-based reductions likely extend to the case without biases. Note that by replacing all biases $b$ in the network with $b \\cdot |y|$, where $y$ is an extra input coordinate, we obtain a bias-free network (albeit with one extra hidden layer, as $|y|=\\max(0,y)+\\max(0,-y)$ needs to be computed at first). With this modification, the respective hardness results should hold also in the bias-free case: if the original network has $k$ affine regions, then the bias-free network has between $k$ and $2k$ affine regions, and the original network is equally zero if and only if the bias-free network is equally zero, but making this rigorous is subject to further research.\n\n>2. Have the authors considered the parameterized complexity of counting linear regions? While the paper establishes strong worst-case hardness results (e.g., #P-hardness for 1-layer networks and ETH-based lower bounds in input dimension), it would be interesting to analyze whether the problem admits fixed-parameter tractable algorithms with respect to natural parameters such as the total number of neurons s(N), the network depth d, or the number of regions R.\n\nWhile the (informal) algorithms presented in Section 6 for counting activation regions and proper activation regions (Definitions 1 and 2) show fixed parameter tractability of the corresponding problems with respect to the number of neurons $s(N)$, many important questions regarding the parameterized complexity of the problems remain open. As stated above, we will explicitly mention these questions in the camera-ready version of the paper.\n\n>1. The paper exclusively analyzes the worst-case computational complexity of counting linear regions. While this is important from a theoretical standpoint, it may not fully capture the behavior of ReLU networks encountered in practice—particularly those trained using gradient-based methods, which are often observed to induce relatively few linear regions.\n\nWe have addressed this comment above.\n\n>2. Although the authors show that region counting is in FPSPACE for some definitions, the algorithms presented are mainly of theoretical interest and not designed for practical implementation. There is little discussion of heuristics, approximations, or tractable special cases.\n\nTheorems 5.7 and 5.8 show NP-hardness of approximation within a factor that is exponential in the input dimension."}, {"review_id": "nWIOmt8h0e", "reviewer": "Reviewer_9Trg", "summary": "This paper studies the computational complexity of counting linear regions of ReLU neural networks. It's shown that while such problem is computationally feasible for one-hidden-layer networks, it becomes inefficient for networks with more than one hidden layers.", "questions": "I believe this paper would be a better fit for TCS venues.", "limitations": "Yes.", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "**Main strength:** the results are novel and technically interesting. In particular, the authors show a sharp phase transition between one and more layers.\n\n**Main weakness:** my main concern is on the relevance and significance to the machine learning community. (1) counting the number of linear regions is not a popular (and not a good one in my opinion, e.g. the highly self-repeating \"saw-tooth\" function) metric for the expressivity of neural networks. (2) deciding the computational complexity of such problem, is even less relevant, since I find no reason to consider it at all in practice.\n\n**Other comments:** the improvement over the result of Wang 2022 seems incremental. The proof uses a similar framework, and the new regime covered isn't significant, since most practical neural networks have depth at least $O(\\log n)$, already covered by Wang 2022. I believe it would be beneficial to discuss more on your technical novelties.\n\nIn section 3, you claim to unify the six definitions, while I found no statements supporting this claim (unless you can somehow show $R_1=O(R_6)$, or rewrite all six with a single notion). This makes this section look somewhat deviating.", "was_revised": true, "final_justification": "I have read through the author's response and other reviews. My main question on the relevance was not resolved by the author's reply. In the meantime, I agree with other reviewers that it's a technically solid paper, and there is certainly no harm to have it.", "rebuttal": "Thank you for carefully reading and evaluating our paper, and for your constructive feedback. We hope to have addressed all questions and comments in the responses below. If you have any further questions, please don’t hesitate to post them - we’ll be happy to clarify them.\n\n>my main concern is on the relevance and significance to the machine learning community. (1) counting the number of linear regions is not a popular (and not a good one in my opinion, e.g. the highly self-repeating \"saw-tooth\" function) metric for the expressivity of neural networks. (2) deciding the computational complexity of such problem, is even less relevant, since I find no reason to consider it at all in practice.\n\nThere are several papers devoted entirely to studying and computing the number of linear regions of ReLU networks (e.g. Pascanu et al. [2014], Montufar et al. [2014], Serra et al. [2018], Hanin and Rolnick [2019], Wang [2022], Goujon et al. [2024]). In our view, this reflects a sustained interest in the topic within the machine learning community. More generally, the number of linear regions is one of the first and most fundamental measures to consider when trying to understand how complex a continuous piecewise linear (CPWL) function is. We do not believe that the relevance of this measure hinges only on Telgarsky’s “sawtooth” function. As evidenced by the cited works, a variety of algorithms have been proposed for counting linear regions. These algorithms for counting linear regions were, for example, used by researchers to investigate why certain architectural or training conditions (e.g. depth, number of training points) lead to a change in network performance. In this context, we see it as natural to study the computational complexity of counting linear regions.\n\n> the improvement over the result of Wang 2022 seems incremental. The proof uses a similar framework, and the new regime covered isn't significant, since most practical neural networks have depth at least $\\mathcal{O}(\\log n)$, already covered by Wang 2022. I believe it would be beneficial to discuss more on your technical novelties.\n\nWhile there are certainly architectures that are deeper, it seems likely that networks of lower depth could be used by commercial companies. In addition, researchers may want to estimate the number of linear regions (and have done so in the past) and use for this purpose wider networks of limited depth - for which our results apply, but those of Wang [2022] do not.\nWe emphasize that our contributions are not incremental and outline our new technical novelties below:\n- In contrast to Wang [2022], we strengthen the hardness results from a depth that grows with input dimension to a constant depth. To achieve this, we build on the ideas from Katz et al. [2017] and construct a network that outputs 1 on a 0-1 input point if and only if the point represents a satisfying assignment to the given SAT instance, and 0 otherwise. The core technical novelty in this improvement lies in how we “nullify” this network’s output outside the vicinity of 0-1 points. While Wang [2022] achieves this by taking the minimum of $n+1$ functions using $\\log(n+1)$ hidden layers to, we design a new “gadget function” that achieves this nullification using only a single hidden layer.\n- Beyond hardness of decision problems, we prove hardness of approximation, which was not addressed in prior work. In Lemma 5.6, we extend our reduction with an additional hidden layer and a second novel gadget function that ensures each satisfying 0-1 point leads to a fixed, predetermined number of linear regions.\n- In Theorem 5.8, we present a novel construction that amplifies inapproximability by summing multiple copies of a “hard” network.\n- Our results also cover six distinct definitions of linear regions, whereas prior work usually only considered one or two definitions. This generality required additional effort: for instance, Theorem 4.2 relies on a reduction from hyperplane arrangement cell counting, which requires carefully orienting hyperplanes to ensure the result holds for all definitions.\n- Finally, in Algorithm 2, we present a novel FPSPACE algorithm for counting affine regions. A key difficulty in this setting is avoiding the need of keeping track of all encountered affine functions explicitly, which would require exponential space. Our approach sidesteps this by enumerating all possible coefficient combinations, thereby iterating over all possible affine functions implicitly, using only polynomial space.\n\n>In section 3, you claim to unify the six definitions, while I found no statements supporting this claim (unless you can somehow show $R_1=\\mathcal{O}(R_6)$, or rewrite all six with a single notion). This makes this section look somewhat deviating.\n\nThe goal of Section 3 was not to assert that all definitions are equivalent or easily relatable to one another (beyond the bounds that we cited from prior work). Rather, the aim of the section is to systematically present the six most widely used definitions and to highlight the subtle but important distinctions between them. To avoid any possible confusion, we are happy to revise the opening sentence of Section 3 to more clearly reflect this intention. Note that it is not possible to obtain significantly better bounds than the trivial bound $R_1\\in 2^{\\mathcal{O}(s(N))} \\cdot R_6$. To see this, consider a hyperplane arrangement $H$ in $\\mathbb{R}^n$ with $n$ hyperplanes that are in general position. This hyperplane arrangement partitions the space into $2^n$ cells. We can construct a ReLU network $N$ with $2n$ ReLU neurons such that, for each hyperplane in the hyperplane arrangement, there are exactly two neurons inducing that hyperplane such that their contributions cancel out. The resulting network computes the zero function, and therefore has only one affine region (i.e., $R_6=1$). However, the network $N$ has at least $2^n$ activation regions ($R_1>=2^n$). Inserting $s(N)=2n$ yields $R_1>= 2^{s(N) / 2} \\cdot R_6$.\n\n>I believe this paper would be a better fit for TCS venues.\n\nWhile the theoretical focus of the paper is indeed a limitation as we acknowledged, we do not view this as a weakness. In our view, pure theory papers like ours are a valuable contribution to NeurIPS. Similar computational complexity theory papers have been published at NeurIPS (e.g. Blum and Rivest [1988], Livni et al. [2014], Barceló et al. [2020], Bertschinger et al. [2023]).\n\nReferences.\n- Training a 3-node neural network is NP-complete, Blum and Rivest. NeurIPS 1988.\n- On the Computational Efficiency of Training Neural Networks. Livni et al. NeurIPS 2014.\n- Model Interpretability through the Lens of Computational Complexity. Barceló et al. NeurIPS 2020."}]

Author rebuttal:

Meta-review: This paper offers a comprehensive theoretical study of the computational complexity of counting linear regions in ReLU neural networks. It examines six non-equivalent definitions from the literature, clarifies their relationships, and establishes hardness results: #P-hardness for shallow networks, NP-completeness for deeper networks with a constant number of hidden layers (with corresponding inapproximability results in both cases), and PSPACE upper bounds for certain definitions.

Initial concerns, such as reliance on worst case analysis, were largely addressed in rebuttal. Some of the discussion revolved around a fundamental concern, voiced most strongly by Reviewer 9Trg, which questioned whether the problem studied constitutes a direct practical objective for the ML community. As the field of deep learning evolves, new concepts and methods (in this case established and powerful tools from theoretical computer science) are increasingly introduced to address important open questions. A recurring challenge is assessing how well such contributions fit within the broader context of deep learning theory and whether they provide practically relevant new insights. In this case, the consensus leaned toward acceptance on the grounds of the fundamental importance that linear regions play in the theoretical understanding of ReLU networks (including expressiveness and optimization), and overall the paper was praised for its systematic treatment of definitions, its rigor, and its novel hardness proofs. The authors are encouraged to incorporate the valuable comments provided by the reviewers and to further emphasize the empirical aspects underlying the study of linear regions.
Decision: Accept (poster)