Parameterized Hardness of Zonotope Containment and Neural Network Verification
Authors: Vincent Froese
Moritz Leo Grillo
Christoph Hertrich
Moritz Stargalla
Venue: ICLR 2026 Poster (2026)
Keywords: Parameterized Complexity
Exponential Time Hypothesis
Norm Maximization
Polyhedral Geometry
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posted by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification.
In particular, we prove that deciding positivity (and thus surjectivity) of a function $f\colon\mathbb{R}^d\to\mathbb{R}$ computed by a 2-layer ReLU network is W[1]-hard when parameterized by $d$.
This result also implies that zonotope (non-)containment is W[1]-hard with respect to $d$, a problem that is of independent interest in computational geometry, control theory, and robotics.
Moreover, we show that (a) approximating the maximum within any multiplicative factor in 2-layer ReLU networks, (b) computing the $L_p$-Lipschitz constant for $p\in(0,\infty]$ in 2-layer networks, and (c) approximating the $L_p$-Lipschitz constant in 3-layer networks are all NP-hard and W[1]-hard with respect to $d$.
Notably, our hardness results are the strongest known so far and imply that the naive enumeration-based methods for solving these fundamental problems are all essentially optimal under the Exponential Time Hypothesis.

Published as a conference paper at ICLR 2026
PARAMETERIZED HARDNESS OF ZONOTOPE CON- TAINMENT AND NEURAL NETWORK VERIFICATION
Vincent Froese
Moritz Grillo
Technische Universität Berlin
Max Planck Institute for Mathematics in the Sciences moritz . gr 1o0mi s. www. de
Algorithmics and Computational Complexity vincent. wincent.froeseeeeee.. froese@tu-berl www.bbbrriinnd... .in.de
Christoph Hertrich
Moritz Stargalla
University of Technology Nuremberg christoph. hert eeaerrich@ute
University of Technology Nuremberg
moritz.stare la l@@ut..de
ABSTRACT
Neural networks with ReLU activations are widely used model in machine learn- ing. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing inter- est in the (parameterized) computational complexity of determining these prop- erties. In this work, close several gaps and resolve open problem posted by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, positivity (and thus surjectivity) of a function f: Rd - R computed by a 2-layer ReLU network is W[1]-hard when parameterized by d. This result also implies that zonotope mon-))contaimmet is W[1]-hard with respect to d, a problem that is of independent interest in computational geometry, control theory, and robotics. Moreover, we show that (a) approximating the maximum within any multiplica- tive factor in 2-layer ReLU networks, (b) computing the Lp-Lipschine constant for (0, oo] in 2-layer networks, and (c) approximating the Lp-Lipschitz con- stant 3-layer networks are all NP-hard and W[I]-hard with respect to d. No- tably, our hardness results are the strongest known so far and imply that the naive enumeration- basedd methods for solving these fundamental problems are all essen- tially optimal under the Exponential Time Hypothesis.
prove that deciding
INTRODUCTION
Neural networks with rectified linear unit (ReLU) activations are a common model in deep learning. In practice, such networks are trained finite datasets and expected generalize reliably to unseen inputs. However, even minor perturbations of the input may lead to unexpected or erroneous outputs (Szegedy et al. 2014). This highlights the importance of certification of trained models, which in turn requires a detailed understanding of the functions computed by ReLU networks.
A central problem in this context network verification: Given a subset of inputs X, the question is whether the network's 's outputs are guaranteed to lie within a prescribed set y, Commonly, the sets X and y take the form of balls or are specified by linear constraints. This question has received increasing attention in recent years, particularly due to the deployment of neural networks in safety- critical applications (Bojarski al. 2016 Weng al. 201 Sa
Kouvaros & Lomuscio 2021 Rössig & Petkovic, 2021 Katz et al. 2022). Recently, Froese et al. (2025b) established connection be- tween the basic verification task to decide whether 2-layer ReLU network attains a positive output (which is equivalent to surjectivity) and the classical geometry problem of zonotope contaimment The latter asks whether one zonotope is contained within another, a question that has been exten- sively studied due to its applications in areas such robotics and control (Sadraddini & Tedrake 2019 Gruber & Althoff 2020 2021 Kulmburg & Althoff 2021 Yang et al. 2022 Kulmburg et al, 2025

---

Published as a conference paper at ICLR 2026
Beyond verification, robustness is often crucial requirement since trained networks are typically expected to be insensitive to small imput perturbations. This property is commonly quantified in terms of the network's Lipschitz constant, which should ideally be small (Virmaux & &camaa 2018
Weng et al. 2018b Fazlyab et al.
2019
JJrdann & Dimakis 2020;
Bhowmick et al.
2021 Splittger
ber 2026).
Network verification (Katz et al.
2022 Sälzer & Lange 2022 Froese et al. 2025b), estimating the
Lipschitz constant (Virmaux & Scaman 2018 Jordan & Dimakis 2020) and zonotope containment (Kulmburg & Althoff 2021) are all known to be (co)NP-hard. This intractability is closely linked to the curse of dimensionality: As the input dimension d grows, the search space becomes prohibitively large. A natural follow-ur up question is whether these problems become tractable for oow-dimensional input spaces. This perspective often assumed to lie near a low-dimensional submanifold of the input space. Motivated by this, recent work has studied the parameterized complexity of neural network problems such as training (Arora et al. 2018 Froese et al. [2022] Brand et al., 2023 Froese & Hertrich (023) and verification Frrosee et al. 2025b). see also Gannian 2026) for a survey. Notably, while checking injectivity of
particularly relevant since, in practice, high-dimensional data
a 2-layer ReLU network with n hidden neurons can done in (d + 1) n ((1) time (that is, fixed- parameter tractability with respect to d) (Froese et al. (025b), the parameterized complexity status of network verification (in particular positivity) and the Lipschitz constant have been posed as open problems at COLT '25 (Froese et al. 2025a).
1.1 OUR CONTRIBUTIONS
We answer the aforementioned questions by proving W[T]-hardness for the parameter input dimen- sion (thus excluding -aremmprreetter tractability under standard complexity assumptions). More- over, we show that solving these problems via simple "brute-force" enumeration of the linear regions of the network's function is essentially optimal under the Exponential Time Hypothesis (ETH).
In Section we give a reduction from the well-known MULTICOLORED CLIQUE problem to net- work verification which the network's input dimension depends linearly on the clique size. This reduction forms the basis for our hardness results and yields strong lower bounds based on the ETH. The key difficulty here is that the input dimension must scale linearly with the clique size (in con- trast, standard NP-hardness reductions allow the input dimension to grow without restriction).
Network Verification. We study the (P-hard problems of deciding positivity, surjectivity, and approximating the maximum of a 2-layer ReLU network f: Rd + R (with hidden neurons), and also the problem of deciding whether a 3-layer ReLU network computes the constant zero func- tion. All these problems are special cases of (complements of) verification. For example, positivity corresponds to checking whether there exists æ E Rd with f(x) > O, that is, f(R") g (-20, 0j. All these problems can be solved in n 0(4) poly (N) time with simple "brute-force" enumeration algorithms (see Section 2). In Section 4 we prove W[1] -hardness with respect to for all problems, thereby resolving the open question by Froese et al. (2025a). Our reductions imply a running time lower bound of n R(()) pooly(N) based on the ETH which shows that the simple enumeration algo- rithms are essentially optimal. In particular, this implies an R(d)) poly(NN-tiin lower bound for the general network verification problem.
Zonotope Containment. In Section 5] we study the coNP-hard problem of deciding whether a zonotope C Rd (given by its generators) is contained in another zonotope Z' C Rdd Based on a duality of 2-layer ReLU networks and zonotopes, we obtain W[1] hhrddhasss with respect to d and an analogous running time lower bound of n (((() (oly(N)) assuming the ETH which shows that the simple vertex enumeration algorithm is essentially optimal.
Lipschitz Constant. Virmaux & Scaman (2018) proved that computing the Lz-Lipschitz constant of a 2-layer ReLU network is NP-hard. In Section 6, we extend this to NP-hardness for every p E (0, oo] and even - with respect to d. Approximating the Ly-Lipschitz constant within any multiplicative constant for 3-layer ReLU networks is known to be NP-hard (Jordan & Dimakis, 2020 Froese et al. 2025b). We also extend this result to W[1] harddess with respect to d. Again, our reductions imply running time lower bounds matching the running times of simple enumeration algorithms. On the positive side, show that for the restricted class of input convex networks,
2

---

Published as a conference paper at ICLR 2026
computing the Li-Lisschitz constant is polynomial-time solvable and the L -Lipschitz constant is fixed- parraeerree tractable (FPT) with respect to d. In Section 7 we discuss the equivalence between Lipschitz constant computation and norm maximization zonotopes and present randomized FPT-approximation algorithm, using results from subspace embeddings.
Limitations. Our paper is clearly of purely theoretical nature. We aim for a thorough understand- ing of the problems from computational complexity perspective. Hence, our results are naturally worst-case results. Although the algorithms we give are essentially optimal in terms of running time (assuming the ETH), it might be possible to achieve better running time by reducing the constant hidden in the exponent. Moreover, additional assumptions on the network structure might render the problems tractable (as in the case of input convex networks for the L Lı-Lisschitz constant). A full literature review (e.g., for the broad field of network verification) is beyond the scope of this paper.
1.2 FURTHER RELATED WORK
Various heuristic methods for network verification have been proposed. including interval bound propagation (Gowal et al.] 2018 DeepZ (Wong al. 2 DeepPoly (Singh al.. (019). multi-
neuron verification Ferrari et al. (2022). ZonoDual (Jordan et al. 2022), and cutting planes (Zhang al. 2022). Baader al. (2024) Mad|Mao et al. (2024) study the expressivity of convex relaxations
that are often used in practical network verification algorithmss Ly- maximization on zonotopes
also known as the Longest Vector Sum problem and has wide range of upplications in pattern recognition, clustering, signal processing, and analysis of large-scale data (Baburin & Pyatkin 2007]]
Shenmaier 2018 2020). Special cases were studied before (Bodlaender et al.) 1990 Ferrez et al, 2005).
2 PRELIMINARIES
Notation. For N, we define [n]] = {1,.... [ll....,ni m). For k. N,k S define ( [n] | k]. A function f: R2 ~F is positively homogeneous if f(z)) Af(x) holds for all E IRd and X 2 O. Given generator matrix A =
= (A
) E Rdxx, the corresponding
zonotope is Z(A) = Ei=1 conv ((0, a;3), where the sum the Minkowski sum of the generators.
4p Lipschitt Constant. For p E (0, co) and a vector x E IRd, we define || = (Σ [mp)))
and for p = oo we set ||||> == ma |zg]- For p E [1, oo]. the function Ilp is the Lop-orrm and for p E (0, 1), the Lu-quasinorm The Lo-function is defined by ||æe||o == Hi E [d] xs A OH|-
The LipLicchhitz constant of function f is Lp( supazy [(x) f(wlll
-x-vllp VII
ReLU Networks. A ReLU layer with d inputs, outputs, weights W E Raxd and biases b R. computes the map Φwas Rdd - Thm x >> max(0, Wx + b). where the maximum is applied in each component. A ReL.U network with & 2 layers and one-dimensional output is defined by é weight matrices W. E R2 X and biases by E R for E [c], where no = d,..., ny = 1 E N+, and computes the continuous piecewise linear (CPWL) function f: 12d IR with
((x) We (ow, 1. о (ww,,,) (x)) be.
Observe that activation function is applied in the output layer. The l - 1 ReLU layers also called hidden layers. The width and size of the network are max(n .i, 1 and Σ/=1 14. respectively. Additional details can be found in Appendix A
Maxout Networks. A 2-maxout layer with inputs, m. outputs, two weight matri- ces W(), W2 E Rdxd and two bias vectors ((1, 6(1,)(2) ((2) E RT computes the map ('wa), www. :(a): Rd Rmm I h max(W(")x + ((1, w(2) x + b(2),, where the maximum is applied in each component. A 2-maxout network is defined analogously to a ReLU network, re- placing the ReLU layers Φw..., with 2-maxout layers 1o W ( a(e) for all i E [e - 1]. We
further note that ReLU networks form a subclass of maxout networks by choosing wi()) 0 and
3

---

Published as a conference paper at ICLR 2026
0 0 for all i [e 1]. Moreover, 2-maxout networks model skip connections using max (2, x) = x.
Polytopes and Duality. There is duality between positively homogeneous convex CPWL func- tions from Rd to R (the set of which denoted Fa) and polytopes in Rd (denoted Pa). which we will briefly sketch. Any function f E Fa can be written as f(x) = max I, _,..., ag 2) for some a, E gd and its Newton polytope is Newt(f) == conv (onv(fa ag H). Equivalently, f is the support function of Newt(f), that is, f(x) = maXyeNewr(f) x. The map y: Fa + Pa. defined by f + [f) is a bijection satisfying (f+g) = +(()) and (maa((s.) = conv (onv()(()Uupg)) where + denotes pointwise addition or Minkowski sum, respectively.
Parameterized Complexity. We assume basic knowledge on computational complexity theory. Parameterized complexity is multivariate approach to study the time complexity of computational problems (Cygan et al. 2015] Downey & Fellows 2013). A parameterized problem S E' x N consists of instances (ar, k) where encodes a classical problem instance and i is parameter. A parameterized problem L is fixed-parameter tractable (contained the class FPT) if it can be solved in f(k) (2:))-(2//00)) (x] time, where f is an arbitrary function that only depends on k. The class XP contains all parameterized problems which can be solved in polynomial time for constant parameter values, that is, in f(k) |ız|s(A) time, where g is an arbitrary function that only depends on k. It known that FPT Ş XP. The class W[I] can be defined as the set of all parameterized problems which can be reduced to CLIQUE (with parameter solution size) via parameterized reduction. It is known that FPT S W[1] in FPT (namely the W[I]-hard problems such as CLIQUE). A parameterized reduction from L to L' is an algorithm that maps an instance (ær k) in fkk |xx] (1)) time to an instance (x', k') such that k' S g(k) for an arbitrary function g and (z. k)
[ XP and it widely believed that W[1] contains problems which are not
and only if (a', K) L'.
The Exponential Time Hypothesis (Impagliazzo & Paturi 2001) states that 3-SAT on n variables cannot be solved in 20(n) time. The ETH implies FPT of W[1] (which implies P NP), as well as running time lower bounds: For example, CLIQUE cannot be solved in p(k) ( (k) time, where is the size of the requested clique and is the number of nodes in the graph (Cygan et al. 2015).
2.1 PROBLEM DEFINITIONS AND WARM-UP
For given generator matrices A E Rdxx and B E Rdxm, and scalar L E R, we consider the following problems:
ZoNOTOPE CONTAINMENT: Is Z(A) C Z())
L.p-MAx ON ZONOTOPES: Is max |>>||p 2 L.?
For an E-layer ReLU network defined by weight matrices W. E B and biases b; Rd for i E [[] where d == To,,..., The = E N+ that computes the function f: IRd + R, f(x) = ow, b. (z) + by. we consider the following problems:
We (ow
&LLAYER RELU POSITIVITY: Is there an Rd such that f(x) > 0?
Ê-LAYER RELU SURJECTIVITY: f surjective (that is, Vy 3r E Rd f(x) = y)?
(-LAYER RELU LIILLIPCHITZ CONSTANT: Is L,()) 2 L?
In fact, all these problems are known to be in XP for the parameter d (simply enumerate vertices of zonotopes and linear regions of ReLU networks; see Appendix B for more details).
Theorem 2.1. ZONOTOPE CONTAINMENT and 1.p-MAX ON ZONOTOPES can be solved in On---1 poly(N)) time (where n is the number of generators and N the input bit-length).
Theorem 2.2. f-LAYER RELU POSITIVITY, Ê-LAYER RELU SURJECTIVITY, Ê-LAYER RELU Lp- LIPLICICIT CONSTANT, computing the maximum of l-layer ReLU network over a polyhe- dron and deciding whether an l-layer ReLU network computes the zero function can be solved in (n((f1))d (N)) time (where n is the network width and N is the input bit-length).
4

---

Published as a conference paper at ICLR 2026
s,lo, 0)
p.(x)
10
6
7
8 9
10
H6.1
+
Weene
10
Figure I: Spike function 8r, a colored graph (top left).
Figure Penalty function Pe-
Node labels: Wr.1 = 1, 1,0r2 = 2, = 4, W1,2 = 8. Edge
lahels: 411,1,1 = 5, 24,21111 6, 1,,2 9, 4422,122 10.
In particular, prove in Appendix B that network verification for ê-layer ReLU networks f Rd R" is solvable in (fn((-Ija poly(N)) time, assuming that X' and Y are polyhedra in halfspacc representation. Later, we will prove that, assuming the ETH, the 2-layer or the 3-layer versions of all of these problems cannot be solved in p(d) No(() time for any function p. which means that the O(n poly(N))- and On poly )oly(())-ttmne) algorithms (for 2- and 3-layer networks) are essentially optimal with respect to the runtime dependency on d. Note that hardness results for 2- or 3-layer networks also imply hardness for deeper networks with l 2 layers: simply concatenate the or 3-layer network with trivial additional layers that compute the identity map.
REDUCTION FROM MULTICOLORED CLIQUE
In this section, we present parameterized reduction which forms the basis for the hardness results for all our considered problems. (All proofs that are omitted from the main text as well as some auxiliary statements can be found in Appendix B We reduce from the following problem.
MULTICOLORED CLIQUE
Input: A graph = (V = VÚÚ.... ... .V,, E), where each node in V; has color i. Does G have k-colored elique (a elique with exactly node of each color)?
Question:
MULTICOL.ORED CLIQUE is NP-hard, W[1]-hard with respect to & and not solvable in p(k) IV time for any computable function p assuming the ETH (Cygan et al. 2015).
Proposition 3.1. For every instance (G = (V = Vi.... UV, E), k) of MULTICOLORED CLIQUE, it is possible construct polynomial time 2-layer ReLU network computing function f: R and max f(x) S le +()
such that max f(x) k (*) if and only if G contains k-colored clique
otherwise.
Proof Sketch. Let (G = (V VÚ. .V,, E), be an instance of MULTICOLORED CLIQUE, where V. = {Ve. nodes have color and We assign each node Ve,s a unique label Wa, E N such that every edge {uy,á, "t,5} gets unique label Wr.id.y = Wr, + w1,; (using Sidon sets, see Appendix B for details).
and = Un (())) E,,, where E,, denotes the set of edges whose
For every color pair (r, ((%), introduce spike function $ R J0, 1] (see Figure 1b that is zero everywhere except for a set of |Eru parallel stripes in which 8,,1 forms spike, that is, goes up from 0 to and goes down from 1 to again. The spike function attains value if and only if the sum of its inputs is equal to Wr,i for some edge {Ur,s, "1,}} E E,,. The spike function can be implemented with 3 E,El neurons. For every color c E [k],, we create a penalty function Pe: R (0, 1] (see Figure 2) that has narrow spike around the value We, for each node Ve, and is zero everywhere else. The penalty function Pe can be implemented with 3n, neurons.
By computing all spike and penalty functions in parallel and summing them up, obtain 2-layer ReLU network with 3(V + [F]) ReL.U neurons that computes f R [0, k (+) with
5

---

Published as a conference paper at ICLR 2026
0.5
405
03
0.5
1.5
15
0.5
D
43
-15
0
12
Figure 3: Homogenization: the function max(O, 2x 1) max (0, 4r 4) + max(0, 2z - 3) +
(left) turned into max(0, 2x y) max(0, Ax 4y) max(0, 2x 3y) 41yl (right).
Σ (M)))
8r, 8r,( vi) + Σ Pe(Ftc)
=
cE
Next, show that if there exists a k-colored clique (u1,a)...., Uk in G. then f(wwlar.... Wk.oz )) = k ( On the other hand, we show that if there point x" E IR* with f(x*) > k + ( 1, then G' has a k-colored clique. The idea is that in this case, all spike and penalty funetions must have positive output. For the penalty functions, this means that ev- ery imput value z must be close to value We.a, which corresponds to the node Ve,a. Since the spike functions only give positive output if the two node inputs correspond to adjacent nodes, the nodes U1.11 Uk then form a k-collored clique in G.
In the following, will modifications of this construction prove hardness results. All (parameterized) reductions are in fact polynomial-tin time reductions and thus also prove NP-hardness. We will only state this explicitly if the NP-hardness of the problem was not previously known.
4 HARDNESS OF NETWORK VERIFICATION PROBLEMS
We first prove W[1]-hardness (w..t. d) of 2-LAYER RELU POSITIVITY. The NP-hardness of 2- LAYER RELU POSITIVITY was established by Froese et al. (025b). We prove W[]]-hardness via the reduction from Proposition 3.1 which relies the of biases. To extend the hardness result to other problems, we need to show a stronger statement: that 2-LAYEER RELU POSITIVITY remains W[1]-hard even when all biases equal to zero. For this,
homogenized ReLU networks.
Definition 4.1. Given a 2-layer ReLU network with single output neuron, its homogenization is the ReLU network (with all biases equal to zero) that is obtained by adding an extra input variable the network, replacing biases b of neurons in the first hidden layer by y and replacing the bias b of the output neuron by lyl b using two extra neurons in the hidden layer.
Figure 3 iillustrates the effect of homogenization on the function of 2-layer ReLU network.
Theorem 4.2. 2-LAYER RELU POSITIVITY is W[I]-hard with respect to d and not solvable in p(d) (o(() time (where N is the input bit-length) for any function p assuming the ETH, even if all biases are zero.
Proof Sketch. Setting the output node bias of the ReLU network constructed in the proof of Proposi-
tion 3.1 -ー (e) yields network that has positive output if and only if the graph from the MULTICLLORED CLIQUE instance contains a k-colored clique. We then show that homogenizing this network preserves this equivalence, which yields parameterized reduction from MULTICOL.-
ORED CLIQUE to 2-LAYER RELU POSITIVITY without biases (and thus proves W[a]-hardness). Note that the input dimension d of the constructed network is k 1. Hence, any algorithm solving 2-LAYER RELU POSITIVITY in p(d) No(d) time would imply algorithm for MULTICOLORED CLIQUE running in p(k) [V])( time (since N (L])(1) contradicting the ETH.
n

---

Published as a conference paper at ICLR 2026
Theorem 4.2 also implies W[1]-hardness w.r.t. the input dimension d for approximating the maxi- mum of 2-layer ReLU network over a polyhedron within any multiplicative factor. Froese et al. 20256 Corollary 13) showed that approximating this value is NP-hard.
Corollary 4.3. Approximating the maximum of a 2-layer ReLU network over a polyhedron within any multiplicative factor is W[1]-han with respect to its input dimension d and cannot be done in p(d) Nold) time (where N is the input bit-length) for any function p assuming the ETH.
By adding another hidden layer with single ReLU neuron to the network constructed the proof of Theorem 4.2 we obtain 3-layer ReLU network that has a non-zero output if and only if the original 2-layer network has a positive output. This yields the following corollary.
Corollary 4.4. The problem of deciding whether a 3-layer ReLU network computes a non-zero function is ]-hrd with respect to its input dimension and not solvable in p(d) No(d) time (where N is the imput bit-length) for any function p assuming the ETH.
The NP-hardness of the above problem was established by Froese et al. (2025)). For 2-layer net- works, it is solvable in polynomial time (Froese al. 2025b). which holds also in the presence of biases (Stargalla et al. 2025). Thus, Corollary 4.4 draws an even clearer boundary between the computational complexity of this problem in the 2-layer and 3-layer cases.
Froese et al. (2025)) proved NP- Narhhedesss of 2-LAYER RELU SURJECTIVITY and asked whether the problem is fixed-parameter tractable with respect to d. We give a negative answer to this question.
Theorem 4.5. 2-LAYER RELU SURJECTIVITY is W[1]-hard with respect to d and not solvable in p(d) No(d) time (where N is the input bit-length) for any function p assuming the ETH.
Proof. Recall that a positively homogeneous function Rd + R is surjective if and only if there exist two points vt, _ Rd such that g(v+) 0 and g(v < 0. The positively homogeneous function f: I=++1 + R of the 2-layer ReLU network from the proof of Theorem 4.2 is in fact
surjective if and only if it has positive point, as f(0, 1) <
HARDNESS OF ZONOTOPE NON-CONTAINMENT
In this section, we prove W[1 -harddesss for ZONOTOPE CON-CONTAINMENT, the complement of ZONOTOPE CONTAINMENT. ZONOTOPE CONTAINMENT is coNP-complete, and can be solved in O(n-11 ((I=-))oly(A') time (where N is the input bit-length) by enumerating the vertices of one zono- lope. but fixed-parameter tractability with respect to the dimension d remained open so far (Froese) al. 2025a). Moreover, Kulmburg & Altholl (02T showed that containment is equivalent to maximizing certain zonotope norm, making it special case of norm maximization on zonotopes.
Froese et al. (2025b) showed that L-LRY RELU POSITIVITY is equivalent ZONOTOPE Non- CONTAINMENT following from the duality of positively homogeneous convex CPWL functions from T to TR. and polytopes in Rdd We will briefly sketch this equivalence. Let 2-layer ReLUU network without biases be given by g(x) = = >; max w.! x). We can assume without loss of generality that A E 1) due to the positive homogeneity of max(0, w. Eier+ max w. x} - EiEr- max(0, w. x} for vectors wy E Rd I+ U. Defining the zonotopes
x). Hence, g(x)
z = p
max (0, wo;xxz) x}}) = Σ conv wi)),
NEl
NEI+
2
max w. x}) = Σ iEI-
conv((0,
1-7-
holds that g = (2+)) x (2-). By definition of the support function, Z C Z implics (2+) (Z-). Conversely, if y. E - Z-, then there is a separating hyperplane H {y E Rd y x = b) such that y. x > and y x < b for all y E Z Hence, (xx) > (see Figure for illustration). Since also any pair of zonotopes is of this form, 2-LAYER RELU POSITIVITY equivalent to ZONOTOPE NON- NON- C---ANNTAIMNTT... Thus, Theorem 4.2 limlies the following theorem.
Theorem 5.1. ZONOTOPE NON- NON-CONTAINMENT is W [1]-hard with respect to d and not solvable in p(d) (odd time (where N is the input bit-length) for any function p assuming the ETH.
7

---

Published as a conference paper at ICLR 2026
H
Z
Figure 4: An illustration of the equivalence between 2-LAYER RELU POSITIVITY and ZONOTOPE NON-CONTAINMENT. Let H {y E Ed 1 x
b} be a hyperplane that separates y, from Z Then g(x) = maxx y' maxyEz y U b > 0.
HARDNESS OF COMPUTING THE LIPSCHITZ CONSTANT
Jordan & Dimakis 2020) established the NP-hardness for approximating the L,p-Lipschitz constant for p 1 and p 0C for 3-layer ReLU networks within multiplicative factor of S?(N1==) for every constant > O. where N is the encoding size of the ReLU network. The NP-hardness result Froeee et al. (2025b) for 2-LAYER RELU POSITIVITY implies NP-hardness for approximating the Typ-Lipschitz constant for p E [0, oo) within any multiplicative factor for 3-layer ReI.U networks. We extend this by showing W[1]-hardness of the problem.
Corollary 6.1. For all p E [0, oo). approximating the Ly-Lipschitz constant of 3-layer ReLU network by any multiplicative factor is W[1]-hard with respect to its input dimension d and cannot be done p(d) Nold) time (where is the input bit-length) for any function p assuming the ETH.
Proof. Adding hidden layer with a single ReLU neuron to the construction in the proof of Theo- rem 4.2 yields 3-layer network which computes a function with non-zero Lp-Lipschitz constant and only if the original 2-layer network has a positive output. Hence, any multiplicative approxi- mation could be used to decide 2-LAYER RELU POSITIVITY.
Virmaux & Scaman (2018) established the NP-hardness of 2-LAYER RELU I.2 LII-LIPSCITZ CON- STANT. We extend the NP-hardness to E (0, oo) and show W[1]-hardness w.r.t. d.
Theorem 6.2. For all E (0, oc], 2-LAYER RELU Lp-LIPSCHITZ CONSTANT is NP-hard, W[L]- hard with respect to and not solvable in p(d) (o((d) time (where N is the input bit-length) (eenthh)oor for any function p assuming the ETH.
Proof Sketch. First, we show that for any positively homogeneous CPWL function f: Rd - R. we have Lp( = max [f(x)). The idea is now to scale all y coefficients of the function g: R + R computed by the homogenized network constructed in the proof of Proposition 3.1 by a sufficiently small amount E to obtain the positively homogeneous CPWL function R A+1 R. Then, every x* E arg max h(x, 1) has (sufficiently) small entries, as scaling the y coefficients is equivalent to scaling the spike and penalty functions. We then show that (h) is almost equal L max 11x:, 1), we can scale down maximizer xx E arg maxzeR* h(x 1) with y that is only slightly smaller than 1 to obtain a feasible point y (Ir, 1) for max][(=.)) h. [1(2, v) with value [h(y" x, y")l = y" [h("", 1)], which proves L 2 (h, 2 L y" (so I,, R L). We conclude the proof by showing that the hardness of computing L transfers computing (h).. O
On the positive side, we show that for special subclass of ReLU networks, computing the L1- and Los -ipsciit constant is tractable.
Input Convex Neural Networks. A 2-maxout network is input-covvex (ICNN) if the weight ma- trices of all but the first layer have only nonnegative entries, resulting in convex function f(x) max (a x ++bh,.... ag be) The T.pshhipschit constant of f is given by the maximum, taken over all linear regions C' of f, of the Ly-Lipschitz constant f restricted to C, where f(x) a. + be for all x C. Using the well-known equality Ly(g) max || (2) for smooth functions
g Rd TR (Jordan & Dimakis 2020), we derive that the -ipps.ipschizz constant of restricted to
8

---

Published as a conference paper at ICLR 2026
lla the region C' is equal to ||ac و and thus Lp(f) linear region of ||aclle 14 max, |aallg. where || is the dual norm of the Lp-norm Note that the function f of the ICNN has the same Li-Lsccciitz constant as the function g(x) = max{a] z, z,.... ag 3} computed by the same network where all biases are set to 0, which implies that we might assume without loss of generality that the network does not have biases and hence computes a function f that is convex and positively homogeneous.
max
Hertrich & Loho 2024) showed that there is small extended formulation of Newt(f) for a func- tion f computed by an ICNN without biases. More precisely, their proof's reveal that for a function f: Rd - IR. computed by an ICNN, there is polytope Q C Rd+mm and a projection æ: Rd+m -> TR. such that T (Q) = Newt(f) (f) and the encoding size of (Q, v) is polynomial in the encoding size of f, where Q is given in half-space representation. Using this, we prove the following proposition.
Proposition 6.3. Let f: I8 + R be an ICNN with encoding size N. Then Li (if) can be computed in (Nly(N) time and Lisof)) (f) can be computed in O(2 poly(N) time.
Proof. By the discussion above, we can assume without loss of generality that there are no bi- ases and f is positively homogeneous. In this case, the definition of the support function im- plies that Lp(f)
maXyeNewe()) l|s/l.. By Hertrich & Loho (2024), there exists a poly- tope Q and a projection π with poly(N) encoding size such that I,( = maxyeQ (1) For p oo and p 1, this maximization can be reduced to finitely many LPs: Indeed, maxyeQ [V)
tee..et maxyeQ c (V), which requires solving only 2d LPs, while nEQ [b](, = max.e (11]a max c² (V)) which requires solving 2d LPs. Since LPs can be solved in polynomial time, the statements follow.
7 NORM MAXIMIZATION ON ZONOTOPES
We close with a short section describing connection between Lipschitz constants of neural net- works and norm maximization on zonotopes. For 2-layer ICNNS f: IRd - IR, we can restrict ourselves without loss of generality to the case where all output weights are equal to 1. In this case, the Newton polytope Nfwt(f) is zonotope and computing (.) is equivalent to maximizing the dual norm of the Lp norm over this zonotope (see Froese et al. (2025a)).
Baburin & Pyatkin (2077) showed that maximizing the -norm on zonotopes is solvable in polynomial time and maximizing the Lı-norm on zonotopes is parammar tractable for d (our Proposition 6.3 generalizes these results). Note that Theorem [5.1 implies that maximizing a zonotope-norm over zonotope W[1]-hard with respect to the dimension d (since zonotope containment is equivalent to this problem (Kulmburg & Althofi (02T)) For p (1, oo), how- ever, it is an open question whether Lp ty-maxiiization on zonotopes is sxeed-parameter tractable for d (Froese et al. 2025a). [Shenmaier (2018) proved NP-hardness and inapproximability for p E [1, oc) and showed a randomized (sampling based) (1 -)aaprroximation with probability poly(d,
1 - 1/c in time (1 polydd n) for every & E (0. and arbitrary norm. We show that known results from subspace embedding theory can also be used to obtain randomized approxima- tions, which is an interesting application of these results. The worst-case running time, however, is worse, but in practice the actual running time might still be faster. [ozzai et al. (2023) observed that results for & subspace embeddings (Cohen & Pengl (2055) yield zonotope order reductions, that is, approximations of zonotopes with few generators. More precisely, the following can be derived.
Theorem 7.1. There is polynomial-timm time algorithm which, given a matrix A E pdxx and > 0,
outputs a matrix A' E Rddrr with r E O(d de -2) such that with high probability
(1 (1+))) S Z(A) ( +)A(A))
This order reduction yields simple randomized approximation algorithm.
Theorem 7.2. Let ||-I| || be any norm Fd (computable in time T). There is randomized algoritium which, given a matrix A e ddx and >> O, outputs a value a E R in d/ . poly(n)) time (for some constant e > 0) such that with high probability
d/
(1+ S max ||ж||| S (1 + s)a. xEZ(A)
9

---

Published as a conference paper at ICLR 2026
Proof. Note that every norm is convex and convex functions attain their maximum on polytope at a vertex. On input EA, we run the algorithm from Theorem 7.1 to obtain a matrix A' with Old de- columns in polynomial time. The zonotope 2(A') has at most O (r ver-
tices (Zaslavsky 1975), which can be enumerated in O(ra-1) time (Ferrez et al. 2005 We simply return the maximum || ||-value a of these vertices. Then, with high probability, holds (1 + E) = C (A) C (1 + + (AA), which implies
max x =E(++e)- ((A)
|||||| (1+ max |||||| S (1+))a== max ||=|| rEZ(A)
=E(I+c)Z(A)
due to absolute homogeneity of norms.
CONCLUSION
We proved the strongest hardness results for various computational problems related to ReLU net- work verification known so far. Note that nearly all considered problems can be phrased in terms of maximizing a certain norm over a zonotope; a problem with numerous applications in other areas. Most importantly, our results imply that simple "brute-force" enumeration algorithms are basically best possible with respect to the dependency of the running time on the input dimension. Thus, we settled the parameterized complexity of wide range of problems almost completely. Moreover, our results show that it does not help to assume that the network weights are sparse and small, since our constructions use only a constant number of (polynomially bounded) non-zero weights for each ReLU neuron. It is thus not easy to formulate general guidance to circumvent this hardness in practice. One would have to make very specific assumptions on the network structure to ensure that the number of linear regions is small and easy to enumerate. It is not clear which assumptions would be natural here and whether networks trained on real-world data satisfy them. Alternatively, one might use techniques (possibly incorporated into the training process) that guarantee efficient verification or use special architectures (such as ICNNs). We also discussed some tractable cases for restricted subclasses of problems well as randomized FPT-approximation. Overall, our hardness results prove and justify that such techniques and the use of heuristics are indeed required in practice to achieve reasonable running times.
The most prominent open question is the fixed -ked-parrmmter tractability of mm-maximizttionn on zono- topes for p E (1, ))) when parameterized by d. Recall that this is equivalent 2-LAYER RELU Lp-LIPSCHIZ CONSTANT with only positive output weights. As a first step, one might try to find a deterministic FPT-approximation for norm maximization on zonotopes (e.g.. by derandomizing the subspace embedding approach). Also, the complexity of computing Lo(f) for 2-layer ReLU networks is open. Another interesting question is whether running times in O(n"d) for c < 1 can be achieved for the considered problems. Last but not least, we wonder whether 2-LAYER RELU POSITIVITY contained in W[1]. This would settle the parameterized complexity completely.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representattinss 2018.
Maximilian Baader, Mark Niklas Mueller, Yuhao Mao, and Martin Vechev. Expressivity of reLU- networks under convex relaxations. In International Conference Learning Representations, 2024.
A. E. Baburin and A. V. Pyatkin. Polynomial algorithms for solving the vector sum problem. Journal of Applied and Industrial Mathematics, 1(3):268-21) 2007.
Aritra Bhowmick, Meenakshi D' D'Souza, and G Srinivasa Raghavan. Lipbab: Computing exact lip- schitz constant of relu networks. In International Conference on Artificial Neural Networks, pp. 151-162, 2021.
Hans L. Bodlaender, Peter Gritzmann, Victor Klee, and Jan van Leeuwen. Computational complex- ity of norm-mane commmmmximizztoon Combinatorica, 10(2):203-225, 1990.
10

---

Published as a conference paper at ICLR 2026
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. End to end learning for self-driving cars. CoRR, abs/1604.07316, 2016.
Rainie Bozzai, Victor Reis, and Thomas Rothvoss. The vector balancing constant for zonotopes. In 2023 IEEE 64th Anmual Symposium Foundations of Computer Science (FOCS), pp. 1292- 1300. IEFE, 2023.
Coreeliss Brand, Robert Ganian, and Mathis Roeton. New complexity-theoretie frontiers of
tractability for neural network training. Advances in Neural Information Processing Systems, 36, 2023.
Michael B. Cohen and Richard Peng. lp row sampling by lewis weights. In Proceedings of the 47th Annual ACM on Symposium Theory of Computing (STOC' '15), pp. 183-192. ACM, 2015.
Marek Cygan, Fedor V. Fomin, Lukasz. Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipezuk, Michal Pilipezuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
H. Edelsbrunner, J. O' O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 15(2):341-363, 1986.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanović. and Martin Vechev. Complete verification via multi-neuron relaxation guided saunhhandd-oumg In International Conference on Learning Representations, 2022.
J.-A. Ferrez, Komei Fukuda, and Thomas M. Liebling. Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm. European Journal of Operations Research, 166(1):35-4) 2005.
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 Re- search, 14:1775-1790, 2022.
Vincent Froese, Moritz Grillo, Christoph Hertrich, and Martin Skutella. Open problem: Fixed- parameter tractability zonotope problems. Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 6210-6214. PMLR, 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 Learn- ing Theory, volume 291 of Proceedings of Machine Learning Research, pp. 2188 2189. PMLR, 2025b.
Robert Ganian. Parameterized complexity in machine learning. Computer Science Review, 59: 100836, 2026.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness interval bound propagation for training verifiably robust models. CoRR, abs/18 101.111.11.. 12715.. 2018.
Felix Gruber and Matthias Althoff.
Computing safe sets of linear sampled-dat systems. 1EEE
Control Systems Letters, 5(2):385-390, 2020.
11

---

Published as a conference paper at ICLR 2026
Felix Gruber and Matthias Althoff. Scalable robust output feedback mpc of linear sampled- systems. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2563-25700 IEEE, 2021.
Boris Hanin and David Rolnick. Deep ReLU networks have surprisingly few activation patterns. Advances in Neural Information Processing Systems, 32, 2019.
Christoph Hertrich and Georg Loho. Neural networks and (virtual) extended formulations. CoRR, abs/241 00s/2411.03006 1.03006, 2024.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001.
Matt Jordan and Alexandros Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Neural Information Processing Systems, 33, 2020.
Matt Jordan, Jonathan Hayase, Alex Dimakis, and Sewoong Oh. Zonotope domains for lagrangian neural network verification. Advances in Neural Information Processing Systems, 35, 2022.
Guy Katz, Clark W. Barrett, David L.. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: calculus for reasoning about deep neural networks. Formal Methods in System Design, 60(1): 87-116, 2022.
Panagiotis Kouvaros and Alessio Lomuscio. Towards scalable complete verification of ReLU neural networks via dependency-basee based branching. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (ICAA '21), pp. 2643-2650, 2021.
Adrian Kulmburg and Matthias Althoff. On the co-NP co-pl--ompleeensss of the zonotope containment problem. European Journal of Control, 62:84-91 91, 2021.
Adrian Kulmburg, Lukas Schafer, and Matthias Althoff. Approximability of the containment prob- lem for zonotopes and ellipsotopes. IEEE Transactions Automatic Control, 2025.
Yuhao Mao, Yani Zhang, and Martin Vechev. On the expressiveness of multi-neuron convex relax- ations. arXiv preprint urXiv:2410.068116 2024.
Abdul Majid Mian and S Chowla. On the b2 sequences of sidon. Proc. Nat. Acad. Sci. India. Sect. A, 14:344, 1944.
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.
Kevin O' O'Bryant. A complete annotated bibliography of work related to sidon sequences. The Electronic Journal of Combinatories felectronic only]. 11, 2004.
Ansgar Rössig and Milena Petkovic, Advances in verification of ReLU neural networks. Journal of Global Optimization, 81(1):109-152, 2021.
Sadra Sadraddini and Russ Tedrake. Linear encodings for polytope containment problems. In 2019 IEEE 58th conference on decision and control (CDC), pp. 4367-4372. IEEE, 2019,
Marco Sälzer and Martin Lange. Reachability in simple neural networks. Fundamenta Informaticae, 189(3-4):241-259 2022.
A. Schrijver. Theory of Linear and Integer programming. Wiley-Interscience,, 1986.
Vladimir Shenmaier. Complexity and approximation of finding the longest vector sum. Computa- tional Mathematics and Mathematical Physics, 886))8850857, 2018.
Vladimir Shenmaier. Complexity and algorithms for finding a subset of vectors with the longest sum. Theoretical Computer Science, 818:60-73, 2020.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certi- fying neural networks. Proceedings of the ACM Programming Languages, 3(POL.), 2019.
12

---

Published as a conference paper at ICLR 2026
Tom A Splittgerber. Exlipbab: Exact lipschitz constant computation for piecewise linear neural networks. arXiv preprint arXiv:2602.15999 2026.
Moritz Stargalla, Christoph Hertrich, and Daniel Reichman. The computational complexity of counting linear regions in ReLU neural networks. Advances Neural Information Processing Systems, 2025.
Alfred Stöhr. Gelöste und ungelöste fragen über basen der natürlichen zahlenreihe. ii. Journal für die reine und angewandte Mathematik, 194:111-140, 1955.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014.
Aladin Virmaux and Kevin Scaman, Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
Lily Weng, Huan Zhang. Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning. 2018a.
Tsui-W Wei Weng, Huan Zhang. Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference on Learning Representations, 2018b.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. Advances in Neural Information Processing Systems, 31, 2018.
Liren Yang, Hang Zhang. Jean- Baattttt Jeannin, and Necmiye Ozay. Efficient backward reachability using the minkowski difference of constrained zonotopes. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 41(11):3969-3980, 2022.
Thomas Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Memoirs of the American Mathematical Society, 1(154), 1975.
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsich, and Zico Kolter. General cutting planes for bound pooanddropgaaion-baaaa -based neural network verification. Advances in Neural Information Processing Systems, 35, 2022.
13


Reviews:
[{"review_id": "ul4xRuQyt2", "reviewer": "Reviewer_wktp", "summary": "The paper uses the tools of parameterized complexity to prove stronger hardness results for several problems arising within the study of ReLU neural networks (for instance, computing the $L_p$-Lipschitz constant of the network), or that can be linked to it (such as Zonotope Containment). \n\nThe paper relies on parameterized reductions, and more precisely on one main reduction using the W[1]-hard problem Multicolored Clique as a starting point and constructing a 2-layer ReLU network such that the maximum value of the function computed by the network determines whether the Multicolored Clique instance had a solution or not.\n\nAfter obtaining the W[1]-hardness and sometimes ETH-conditional lower bounds for some problems, the authors also use known equivalences or reductions between problems to spread these results and get a more complete picture. As they remark in the conclusion, the common denominator to these problems is that they correspond in a way to maximizing a norm over a zonotope.", "questions": "l141: this means that for $\\\\ell=1$, no ReLU neuron is involved?\n\nl269: why do you need two extra hidden neurons for the bias of the output?\n\nl426: what is the size of the LPs?\n\n\n\nSuggestions and Typos:\n\nl21, abstract: For readability, consider \"Moreover, we show that (a): ....., (b): ....., and (c): ...... are all NP-hard and W[1]-hard ....\".\n\nl174: $L\\\\in \\\\mathbb{R}$, right?\n\nFigure 1: the use of \"r, l\" as colors is technically fine, but it is on a psychological level confusing since it looks like \"right, left\", with the \"right\" being always on the left, in the figure and in expressions. Not necessary strictly speaking, but it might be nice swapping them.\n\nl404: please reformulate, highlighting that the maximum is over linear regions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The theoretical analysis is sound, and yields new results for a variety of problems.\n\nGives a theoretical insight into why the naive enumeration algorithms are somehow optimal for these problems, and fosters more application of parameterized complexity to the field.\n\nFor the $L_p$-Lipschitz constant, the hardness result for the exact computation of 2-layer networks is complemented by a hardness result for the approximation of the  $L_p$-Lipschitz constant of 3-layer networks.\n\nThe paper is well written.", "weaknesses": "It is not clear whether some properties of real-world networks make it possible to circumvent these worst-case theorems. However, I agree this is unavoidable for a theoretic analysis, and the identification of such empirical properties is not the topic of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "v0IfwuKho6", "reviewer": "Reviewer_4wHP", "summary": "The paper presents a collection of (parameterised) complexity results related\nto feedforward neural network (FNN) verification tasks, as well as zonotope\ncontainment.\n\nThe paper presents the following core results: \n- 2-Layer ReLU Positivity: The problem of deciding whether a given 2-layer FNN\n  with ReLU activations can produce an output greater than 0 is W[1]-hard.\n- 2-Layer ReLU Surjectivity: The problem of deciding whether a given 2-layer FNN\n  with ReLU activations computes a surjective function is W[1]-hard.\n- Zonotope Non-Containment: The problem of deciding whether, for two given\n  zonotopes, one is not included in the other is W[1]-hard.\n- 2-Layer ReLU $L_p$-Lipschitz Constant: The problem of deciding whether the\n  $L_p$ Lipschitz constant of a given FNN with ReLU activations is greater than\n  some given threshold is NP- and W[1]-hard.\n\nHere, the class W[1] is the first level of the W-hierarchy widely considered in\nthe theory of parameterised complexity.", "questions": "- Can you provide more details regarding the implications for actual\n          verification tasks, such as positivity, given your W[1]-hardness result?\n- Could you elaborate on why problems such as positivity, surjectivity,\n          or the Lipschitz constant are of significance to the verification\n          community? They seem somewhat abstract or overly simplistic.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents its results in a rigorous and convincing manner,\nproviding compelling insights into the complexity of FNN verification-related\nproblems.\n\nFurthermore, the structure and craftsmanship of the paper are commendable and feel very polished.", "weaknesses": "The paper could improve in several areas:\n- While reading, it sometimes feels like a collection of varied results, somewhat loosely\n  related to FNN verification. Providing more explanation on why these problems are of\n  interest would be beneficial.\n- In the same light, the preliminaries seem to lack a proper definition of the class W[1].\n  It is assumed that many readers may not be fully acquainted with parameterised complexity,\n  which might lead to some confusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qoiqagi6FH", "reviewer": "Reviewer_Druf", "summary": "This paper presents new theoretical results on the complexity of the problem of proving properties of ReLU networks. Specifically, the authors study the parameterized complexity of checking for positivity, checking for surjectivity, and computing the Lipschitz constant of ReLU networks and show that these problems are W[1]-hard. The analysis of these properties centers around mapping 2-layer ReLU networks to the multicolored clique problem. The authors also show how these results can be extrapolated to the zonotope containment problem, which has implications in other domains as well.", "questions": "- What are the practical implications of the complexity results?\n- What should we as a community take from these results as we continue to progress the field of neural network verification?\n- Do these results have any implications for approximate neural network verification techniques?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The theoretical complexity results developed in the paper are the strongest known so far and resolve an open problem.\n- The authors develop results for multiple different neural network verification tasks.\n- The results rely on and have implications for well-studied problems in other domains (multicolored clique and zonotope containment).", "weaknesses": "It is not clear from the paper the practical implications of the derived theory and complexity results. Therefore, it may not be immediately useful for practitioners working on neural network verification tools. Many of the high-performance neural network verification tools used these days rely on overapproximations, and it is unclear how these results might inform decisions for further development in this domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZihfErglRo", "reviewer": "Reviewer_Lmnz", "summary": "This paper studies the parameterized complexity of zonotope containment and some problems related to neural network verification. It extends the prior work and proves the strongest complexity bounds so far. The results shows that under Exponential Time Hypothesis (ETH), brute-force enumeration is asymptotically optimal in complexity.", "questions": "Please address the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The studies problem is relevant, i.e., providing better complexity characterization for certain neural network certification related problems.\n\nThe paper is clearly and rogirously written.\n\nThe results are novel and extend the scientific boundary.", "weaknesses": "It is not clear how these results might influence practice. While knowing the complexities might be interesting, it seems to have minimal impact and guidance on neural network certification practice.\n\nSome related work in the difficulty of neural network is missing: [1] shows that for a two-dimensional simple convex monotone CPWL function, there exists no single-neuron relaxations that can precisely certify any network encoding the function; [2] extends the result and shows that every convex relaxation is incomplete in neural network certification. These works study the theoretical boundary of neural network certification in the practical algorithms, while this work characterizes the difficulty of the general problem.\n\n[1] https://arxiv.org/abs/2311.04015\n\n[2] https://arxiv.org/abs/2410.06816", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)