Complexity of Injectivity and Verification of ReLU Neural Networks

## Abstract

Abstract Neural networks with ReLU activation play a key role in modern machine learning.
In view of safety-critical applications, the verification of trained networks is of great importance and necessitates a thorough understanding of essential properties of the function computed by a ReLU network, including characteristics like injectivity and surjectivity.
Recently, Puthawala et al. [JMLR 2022] came up with a characterization for injectivity of a ReLU layer, which implies an exponential-time algorithm.
However, the exact computational complexity of deciding injectivity remained open. We answer this question by proving coNP-completeness of deciding injectivity of a ReLU layer.
On the positive side, as our main result, we present a parameterized algorithm which yields fixed-parameter tractability of the problem with respect to the input dimension.
In addition, we also characterize surjectivity for two-layer ReLU networks with one-dimensional output.
Remarkably, the decision problem turns out to be the complement of a basic network verification task.
We prove NP-hardness for surjectivity, implying a stronger hardness result than previously known for the network verification problem.
Finally, we reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem.

## 1 Introduction

Neural networks with rectified linear units (ReLUs) are a widely used model in deep learning.
Understanding the functions represented by ReLU networks is a major topic in current research as this enables a better interpretability of learning processes.
Recent works focus on studying elementary properties of these functions such as injectivity; see, e.g., Puthawala et al. (); Haider et al. (); Furuya et al. ().
Injectivity plays a crucial role in many applications where invertibility of a neural network is necessary. Such applications include, for example, generative models, inverse problems, or likelihood estimation; see Puthawala et al. (); Furuya et al. () for a more detailed discussion.

Formally, given weights $\mathbf{W}\in\mathbb{R}^{m\times d}$ and biases $\mathbf{b}\in\mathbb{R}^{m}$ of a fully connected ReLU layer, the question is whether the map $\mathbf{x}\mapsto[\mathbf{W}\mathbf{x}+\mathbf{b}]_{+}$ is injective (here $[\cdot]_{+}$ is the *rectifier* function; see Section 2).
Puthawala et al. () give a mathematical characterization for injectivity of a ReLU layer (see Theorem 3), implying an exponential-time algorithm where the exponential part is upper bounded by $\min\{2^{m},m^{d}\}$.
In terms of *parameterized complexity*, the problem is *fixed-parameter tractable*
with respect to the number $m$ of ReLUs, and in XP with respect to the input dimension $d$.
The complexity status of deciding injectivity of a single layer, however, is unresolved and posed as an open question by Puthawala et al. ().

Another natural and fundamental property of functions to consider is surjectivity.
Hence, to complete the picture alongside injectivity, we initiate the study of surjectivity for ReLU networks, which, to the best of our knowledge, has not been considered before.
Our goal of testing elementary properties of ReLU networks is similar in spirit to *neural network verification*; a research field gaining high interest recently due to its great importance, e.g., for safety-critical systems; see, e.g., Weng et al. (); Rössig and Petkovic (); Kouvaros and Lomuscio (); Katz et al. ().
Here, the question is whether for all inputs from a given subset $\mathcal{X}$, the ReLU network outputs a value contained in a given set $\mathcal{Y}$.
Typically, $\mathcal{X}$ is a box or ball and $\mathcal{Y}$ is defined by some linear constraints.
This problem is known to be coNP-hard if the sets $\mathcal{X}$ and $\mathcal{Y}$ are part of the input; see Katz et al. (); Weng et al. ().
In fact, we show that deciding surjectivity can be considered as a certain network verification task.

##### Our Contributions.

After some preliminaries in Section 2,
we show in Section 3 that deciding injectivity (of a ReLU layer) is coNP-complete (Corollary 7) and
thus not polynomial-time solvable, unless P $=$ NP. Notably, our hardness reduction reveals some interesting connections between cut problems in (di)graphs and properties of ReLU networks via graphical hyperplane arrangements. We believe that these connections between seemingly unrelated areas are of independent interest.

Moreover, our hardness result implies a running time lower bound of $2^{\Omega(m)}$ based on the Exponential Time Hypothesis (Corollary 8).
Hence, the running time $2^{m}$ is essentially optimal.
As regards the parameter $d$, however, in Section 4 we give an improved algorithm running in $O\bigl{(}(d+1)^{d}\cdot\operatorname{poly}\bigr{)}$ time. This yields fixed-parameter tractability (Theorem 12)
and settles the complexity status for injectivity of a ReLU layer.

In Section 5, we establish an interesting connection between the surjectivity of functions computed by ReLU networks and *network verification*. We study surjectivity of ReLU networks with two layers and give a characterization for one-dimensional output (Lemma 13) which implies an XP-algorithm with respect to the input dimension $d$ as a parameter.
We then proceed to show that surjectivity can be phrased as (the complement of) a special case of network verification.
We show that this special case is coNP-hard (Proposition 16), which results from our NP-hardness proof for surjectivity (Corollary 19).

We thereby strengthen the hardness results for the network verification problem from the literature (Weng et al. (); Katz et al. ()) in that we prove hardness for only two layers and one-dimensional output for every possible input subset $\mathcal{X}$ that contains an open set.
In particular, our result implies that the computational intractability does not stem from the set $\mathcal{X}$, but is rather an intrinsic property of the ReLU layer itself.
Finally, we also show that surjectivity (and the verification task) can be formulated as a certain zonotope containment problem.

In Section 6 we conclude and point out interesting directions and open problems for future research.

##### Related Work.

Puthawala et al. () initiated the study of injectivity of ReLU networks. Their result implicitly yields an exponential-time algorithm.
They also mention a connection between injectivity and the *spark* of the weight matrix (that is, the minimum number of linearly dependent rows).
Computing the spark is known to be NP-hard (Tillmann and Pfetsch ()), and also known not to be fixed-parameter tractable with respect to $d$, unless FPT = W[1] (Panolan et al. ()).
Haider et al. () use a frame-theoretic approach to study the injectivity of a ReLU layer on a closed ball.
They give an exponential-time algorithm to determine a bias vector for a given weight matrix such that the corresponding map is injective on a closed ball.
Furuya et al. () study injectivity of ReLU layers with linear neural operators.

The network verification problem is known to be coNP-hard for networks with two layers and arbitrary output dimension (Katz et al. () showed NP-hardness for the complement).
It is also known to be coNP-hard and hard to approximate in polynomial time for one-dimensional output if the number of layers is unbounded (Weng et al. ()).
Several heuristic approaches exist; see, e.g., Jordan et al. (); Rössig and Petkovic (); Kouvaros and Lomuscio ().

Parameterized complexity has also been studied for the training problem for ReLU neural networks by Froese et al. (); Froese and Hertrich ().
In general, understanding the complexity/expressivity of ReLU neural networks is an important task (Hertrich et al. ()).

## 2 Preliminaries

We introduce the basic definitions and concepts involving ReLU neural networks and their geometry which are relevant for this work.

###### Definition 1 .

A ReLU-layer with $d$ inputs, $m$ outputs, weights $\mathbf{W}\in\mathbb{R}^{m\times d}$, and biases $\mathbf{b}\in\mathbb{R}^{m}$ computes a map

$$ $\displaystyle\phi_{\mathbf{W},\mathbf{b}}\colon$ $\displaystyle\mathbb{R}^{d}\to\mathbb{R}^{m},\quad\mathbf{x}\mapsto[\mathbf{W} \mathbf{x}+\mathbf{b}]_{+},$ $$

where $[\cdot]_{+}\colon\mathbb{R}^{m}\to\mathbb{R}^{m}$ is the *rectifier function* given by $[\mathbf{x}]_{+}\coloneqq(\max\{0,\mathbf{x}_{1}\},\ldots,\max\{0,\mathbf{x}_{
m}\})$.

As regards injectivity, Puthawala et al. (, Lemma 3) observe that one can assume without loss of generality that $\mathbf{b}=\mathbf{0}$.
Hence, we omit $\mathbf{b}$ in the following and simplify notation $\phi_{\mathbf{W}}\coloneqq\phi_{\mathbf{W},\mathbf{0}}$.

###### Definition 1 .

##### Geometry of ReLU Neural Networks.

We introduce basic definitions from polyhedral geometry; see Schrijver () for details.
For a row vector $\mathbf{w}_{i}$, the hyperplane $H_{\mathbf{w}_{i}}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{w}_{i}
\mathbf{x}=0\}$ subdivides $\mathbb{R}^{d}$ into half-spaces $H^{+}_{\mathbf{w}_{i}}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{w}_{i}
\mathbf{x}\geq 0\}$ and $H^{-}_{\mathbf{w}_{i}}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{w}_{i}
\mathbf{x}\leq 0\}$. For a matrix $\mathbf{W}\in\mathbb{R}^{m\times d}$, the set of full-dimensional polyhedral cones

$$ $\mathcal{C}_{\mathbf{W}}\coloneqq\biggl{\{}\bigcap_{i=1}^{m}H^{s_{i}}_{\mathbf {w}_{i}}\,\bigg{|}\,(s_{1},\ldots,s_{m})\in\{+,-\}^{m},\,\dim\Bigl{(}\bigcap_{ i=1}^{m}H^{s_{i}}_{\mathbf{w}_{i}}\Bigr{)}=d\biggr{\}}$ $$

subdivides $\mathbb{R}^{d}$ and the set $\{C\cap H_{\mathbf{w}_{i}}\mid C\in\mathcal{C}_{\mathbf{W}},i\in[m]\}$ forms a polyhedral fan. A vector $\mathbf{x}$ in the support $|\Sigma_{\mathbf{W}}|=\bigcup_{\sigma\in\Sigma_{\mathbf{W}}}\sigma$ of the fan $\Sigma_{\mathbf{W}}$ is called a *breakpoint* of $\phi_{\mathbf{W}}$.

For $C\in\mathcal{C}_{\mathbf{W}}$, we define the *active* set $I_{C}\coloneqq\{j\in[m]\mid\forall\mathbf{x}\in C:\mathbf{w}_{j}\mathbf{x}\geq
0\}$ and the matrix $\mathbf{W}_{C}\in\mathbb{R}^{m\times d}$, where

$$ $(\mathbf{W}_{C})_{j}\coloneqq\begin{cases}\mathbf{w}_{j},&j\in I_{C},\\ \mathbf{0},&j\in[m]\setminus I_{C}.\end{cases}$ $$

Note that the map $\phi_{\mathbf{W}}$ is linear on $C$, namely $\phi_{\mathbf{W}}(\mathbf{x})=\mathbf{W}_{C}\cdot\mathbf{x}$ for $\mathbf{x}\in C$.

A *ray* $\rho$ is a one-dimensional pointed cone; a vector $\mathbf{r}$ is a *ray generator* of $\rho$ if $\rho=\{\lambda\,\mathbf{r}\mid\lambda\geq 0\}$.
For each ray $\rho$ of $\Sigma_{\mathbf{W}}$, let $\mathbf{r}_{\rho}$ be an arbitrary generator of $\rho$ and let $\mathcal{R}\coloneqq\{\mathbf{r}_{\rho}\mid\rho\text{ is a ray in }\Sigma_{
\mathbf{W}}\}$.
We make the following simple observation.

###### Observation 2 .

Let $C$ be a pointed polyhedral cone such that $\phi_{\mathbf{W}}$ is linear on $C$ and let $\mathbf{r}_{1},\ldots,\mathbf{r}_{\ell}$ be ray generators of the extreme rays of $C$.
Then, for each $\mathbf{x}\in C$, there are $\lambda_{1},\ldots,\lambda_{\ell}\in\mathbb{R}$ such that $\mathbf{x}=\sum_{i=1}^{\ell}\lambda_{i}\mathbf{r}_{i}$ and $\phi_{\mathbf{W}}(\mathbf{x})=\sum_{i=1}^{\ell}\lambda_{i}\phi_{\mathbf{W}}(
\mathbf{r}_{i})$.

2 implies that the map $\phi_{\mathbf{W}}$ is essentially determined by its values on $\mathcal{R}$, if all cones $C\in\mathcal{C}_{\mathbf{W}}$ are pointed.

###### Observation 2 .

##### Injectivity Criterion.

Puthawala et al. (, Theorem 2) prove the following characterization of injectivity.

###### Theorem 3 ( Puthawala et al. ( 2022 ) ) .

A ReLU-layer $\phi_{\mathbf{W}}$ with $\mathbf{W}\in\mathbb{R}^{m\times d}$ is injective if and only if $\mathbf{W}_{C}$ has (full) rank $d$ for all $C\in\mathcal{C}_{\mathbf{W}}$.

Since any hyperplane arrangement with $m$ hyperplanes in $d$ dimensions defines at most $O(m^{d})$ (also clearly at most $2^{m}$) cells (Zaslavsky ()), Theorem 3 implies an algorithm that solves ReLU-layer Injectivity in $O(\min\{2^{m},m^{d}\}\cdot\operatorname{poly}(S))$ time, where $S$ denotes the input size.

###### Theorem 3 ( Puthawala et al. ( 2022 ) ) .

##### (Parameterized) Complexity Theory.

We assume the reader to be familiar with basic concepts from classical complexity theory like P, NP, and NP-completeness. The class coNP contains all decision problems whose complement is in NP. A decision problem is coNP-complete if and only if its complement is NP-complete.
Clearly, a coNP-complete problem cannot be solved in polynomial time unless P $=$ NP.

A *parameterized* problem consists of instances $(x,k)$, where $x$ encodes the classical instance and $k\in\mathbb{N}$ is a *parameter*. A parameterized problem is in the class XP if it is polynomial-time solvable for every constant parameter value, that is, in $O(|x|^{f(k)})$ time for an arbitrary function $f$ depending only on the parameter $k$. A parameterized problem is *fixed-parameter tractable* (contained in the class FPT) if it is solvable in $f(k)\cdot|x|^{O(1)}$ time, for an arbitrary function $f$.
Clearly, FPT $\subseteq$ XP; see Downey and Fellows () for further details of parameterized complexity.

## 3 coNP-Completeness of Injectivity

In this section we study the following decision problem.

ReLU-layer Injectivity
Input:
A matrix $\mathbf{W}\in\mathbb{R}^{m\times d}$ and a vector $\mathbf{b}\in\mathbb{R}^{m}$.
Question:
Is the map $\phi_{\mathbf{W},\mathbf{b}}$ injective?

We prove that ReLU-layer Injectivity is coNP-complete.
To this end, we show NP-completeness for the complement problem, which based on Theorem 3 and the fact that one can assume w.l.o.g. $\mathbf{b}=\mathbf{0}$ (Puthawala et al., , Lemma 3), can be formulated as follows.

ReLU-layer Non-Injectivity
Input:
A matrix $\mathbf{W}\in\mathbb{R}^{m\times d}$.
Question:
Is there a cell $C\in\mathcal{C}_{\mathbf{W}}$ such that $\operatorname{rank}(\mathbf{W}_{C})<d$?

For the NP-hardness proof, we reduce from the following digraph problem.

Acyclic $2$-disconnection
Input:
A digraph $D=(V,A)$.
Question:
Is there a subset $A^{\prime}\subseteq A$ of arcs such that $(V,A^{\prime})$ is acyclic and $(V,A\setminus A^{\prime})$ is not weakly connected?

The problem is a special case of Acyclic $s$-Disconnection where the goal is to remove an acyclic arc set such that the remaining digraph contains at least $s$ weakly connected components. This more general problem is known to be NP-hard if $s$ is part of the input (Figueroa et al. ()). In Appendix A.1.1 we prove NP-hardness for our special case $s=2$.

###### Theorem 4 .

Acyclic $2$-disconnection is NP-hard.

The proof is based on a reduction from 3-Uniform Hypergraph 2-Coloring(^1^11Also known as Not-All-Equal 3-SAT.) to Matching Cut by Chvátal (). We remark that our reduction implies a running time lower bound based on the Exponential Time Hypothesis(^2^22The Exponential Time Hypothesis asserts that 3-SAT cannot be solved in $2^{o(n)}$ time where $n$ is the number of Boolean variables in the input formula (Impagliazzo and Paturi ()).) (ETH).
As discussed by Kratsch and Le (), there is no algorithm solving a 3-Uniform Hypergraph 2-Coloring-instance $(V,E)$ in $2^{o(|E|)}$ time assuming ETH.
Our polynomial-time reduction in the proof of Theorem 4 constructs a digraph $D$ of size $O(|V|+|E|)$. Notice that $O(|V|+|E|)\subseteq O(|E|)$ since we can assume $|V|\leq 3|E|$ (isolated nodes can trivially be removed).
Hence, any algorithm solving Acyclic $2$-disconnection in $2^{o(|D|)}$ time would imply a $2^{o(|E|)}$-time algorithm for 3-Uniform Hypergraph 2-Coloring.

###### Corollary 5 .

Acyclic $2$-disconnection cannot be solved in $2^{o(|D|)}$ time unless the ETH fails.

Having Theorem 4 at hand, we are ready to prove the NP-completenss of ReLU-layer Non-Injectivity.

###### Theorem 6 .

ReLU-layer Non-Injectivity is NP-complete even if every row of $\mathbf{W}$ contains at most two non-zero entries.

###### Proof sketch.

Containment in NP is easy: The set $I_{C}$ of a cell $C$ with $\operatorname{rank}(\mathbf{W}_{C})<d$ serves as a certificate.
To prove NP-hardness, we reduce from Acyclic $2$-disconnection which is NP-hard by Theorem 4. We sketch the proof here, a detailed proof can be found in Appendix A.1.2.
Given a digraph $D=(V,A)$ with $V=[n]$, we construct a ReLU-layer $\phi\colon\mathbb{R}^{n-1}\to\mathbb{R}^{|A|}$ by

$$ $\phi(\mathbf{x})=(\max\{0,\mathbf{x}_{i}-\mathbf{x}_{j}\})_{(i,j)\in A}$ $$

For every permutation $\pi\in\mathcal{S}_{n}$, function $\phi$ is linear on the cone $C_{\pi}\coloneqq\{\mathbf{x}\mid\mathbf{x}_{\pi(1)}\leq\dots\leq\mathbf{x}_{
\pi(n)}\}$, where we let $\mathbf{x}_{n}\coloneqq 0$. Let $A_{\pi}\coloneqq\{(i,j)\in A\mid\pi(i)\leq\pi(j)\}\subseteq A$ be the (acylic) subset of arcs respecting the (total) order on the nodes induced by $\pi\in\mathcal{S}_{n}$. The set of arcs in the complement $A\setminus A_{\pi}$ is therefore in bijection with the neurons that are active on $C_{\pi}$. Moreover, the digraph $D_{\pi}=(V,A\setminus A_{\pi})$ is weakly connected if and only if

- –
there is a path in the underlying graph of $D_{\pi}$ from node $j$ to node $n$, for all $j\in[n-1]$;
- –
if and only if the standard unit vector $\mathbf{e}_{j}$ is contained in $\operatorname{span}(\mathbf{W}_{C_{\pi}})$, for all $j\in[n-1]$;
- –
if and only if $\mathbf{W}_{C_{\pi}}$ has full rank.

Since the partial order on the nodes induced by an acyclic subset of arcs can be extended to a total order on the nodes, it holds that $\phi$ is not injective if and only if there is $A^{\prime}\subseteq A$ such that $(V,A^{\prime})$ is acyclic and $(V,A\setminus A^{\prime})$ is not weakly connected, proving the correctness of the reduction.
∎

###### Corollary 7 .

ReLU-layer Injectivity is coNP-complete even if every row of $\mathbf{W}$ contains at most two non-zero entries (and $\mathbf{b}=\mathbf{0}$).

Furthermore, the lower bound from Corollary 5 actually transfers to ReLU-layer Injectivity since our polynomial-time reduction in the proof of Theorem 6 yields a matrix where the number of rows/columns
is linear in the number arcs/nodes of the digraph.

###### Corollary 8 .

ReLU-layer Non-Injectivity and ReLU-layer Injectivity cannot be solved in $2^{o(m+d)}$ time, unless the ETH fails.

###### Theorem 4 .

###### Corollary 5 .

###### Theorem 6 .

###### Proof sketch.

###### Corollary 7 .

###### Corollary 8 .

## 4 An FPT Algorithm for Injectivity

The complexity results from the previous section exclude polynomial running times as well as running times subexponential in $m+d$ for deciding injectivity.
Nevertheless, we show in this section that the previous upper bound of $m^{d}$ can be improved to $(d+1)^{d}$.
We achieve this with a branching algorithm which searches for a “non-injective” cell $C$, that is, $\mathbf{W}_{C}$ has rank strictly less than $d$.
The algorithm branches on the ReLUs active in $C$, thus restricting the search space to some cone.
The pseudocode is given in Algorithms 1 and 2.

Figure: Algorithm 1 LayerInjectivity

Figure: Algorithm 2 FindCell

The key idea to bound the running time of our search tree algorithm is to show that there are always at most $d+1$ candidate ReLUs to set active. The candidates are those whose corresponding halfspaces cover the current search space; that is, at least one of them will be active in the sought cell (cf. Algorithm 2 of Algorithm 2).
Helly’s Theorem (Helly ()) ensures that there are always at most $d+1$ such candidates. Using duality of linear programming, we show that these halfspaces can be found in polynomial time. A more detailed proof of the following lemma is given in Section A.1.3.

###### Lemma 9 .

Let $C\subseteq\mathbb{R}^{d}$ be a cone and let $\{\mathbf{w}_{1},\ldots,\mathbf{w}_{n}\}\subseteq\mathbb{R}^{d}$ be such that $C$ is covered by the corresponding half-spaces, that is, $C\subseteq\bigcup_{i=1}^{n}H_{\mathbf{w}_{i}}^{+}$. Then, there exists a subset $A\subseteq[n]$ of size at most $d+1$ computable in polynomial time, such that $C\subseteq\bigcup_{i\in A}H_{\mathbf{w}_{i}}^{+}$.

As regards the correctness of our algorithm,
assume that there exists a vector $\mathbf{x}\in\mathbb{R}^{d}$ such that $\operatorname{rank}(\{\mathbf{w}_{i}\mid\mathbf{w}_{i}^{T}\mathbf{x}\geq 0\})=
k<d$. Then, after every branching, $\mathbf{x}$ is contained in some cone that is the search space of FindCell, that is, $\mathbf{c}_{i}^{T}\mathbf{x}\geq 0$ for all $i\in[n]$. Notice that every branching increases the number of linear independent neurons that are active in the current cone by one. Thus, after at most $k$ branchings, FindCell finds a cone where the map is not injective. Conversely, if the algorithm outputs an $\mathbf{x}\in\mathbb{R}^{d}$, then the matrix $\mathbf{W}_{\bar{C}}$ corresponding to the cone $\bar{C}\coloneqq\{\bar{\mathbf{x}}\mid\forall i\in[n]:\mathbf{c}_{i}^{T}\bar{
\mathbf{x}}\geq 0\}$ containing $\mathbf{x}$ cannot have full rank; otherwise, Algorithm 2 in FindCell would have output “no”.

###### Lemma 10 .

Algorithm 1 is correct.

Lemma 9 ensures that we can always branch on $d+1$ neurons. Furthermore, the number of active neurons increases after every branching by one. Hence the search tree has at most $(d+1)^{d}$ nodes.

###### Lemma 11 .

Algorithm 1 runs in $O((d+1)^{d}\cdot\operatorname{poly}(S))$ time, where $S$ denotes the input size.

We provide detailed proofs of Lemma 10 and Lemma 11 in Section A.1.4 and Section A.1.5, respectively.
We conclude our findings in the following theorem.

###### Theorem 12 .

ReLU-layer Injectivity is solvable in $O((d+1)^{d}\cdot\operatorname{poly}(S))$ time, where $S$ denotes the input size.

Deciding injectivity for a deep neural network, that is, a concatenation $\Phi=\phi_{n}\circ\cdots\circ\phi_{1}$ of layer maps, is even more involved. Clearly, if all layer maps $\phi_{\ell}$ are injective, then also $\Phi$ is injective. The converse does not hold, however, since $\phi_{\ell}$ only needs to be injective on the image $(\phi_{\ell-1}\circ\cdots\circ\phi_{1})(\mathbb{R}^{d})$ for all $\ell\in[n]\coloneqq\{1,\dots,n\}$. Nevertheless, the coNP-hardness from Corollary 7 implies coNP-hardness for the general case. However, it is unclear whether the problem is still contained in coNP or in FPT when parameterized by $d$.

###### Lemma 9 .

###### Lemma 10 .

###### Lemma 11 .

###### Theorem 12 .

## 5 Surjectivity and Verification

In this section, we study the task to decide whether a given ReLU network computes a surjective map. This question does not make sense for a single ReLU layer, since ReLU outputs are always non-negative.
Hence, we study networks with two layers: one hidden layer with $m_{1}$ neurons (with weights $\mathbf{W}_{1}\in\mathbb{R}^{m_{1}\times d}$ and bias $\mathbf{b}_{1}\in\mathbb{R}^{m_{1}}$) with ReLU activation, and one output layer with $m_{2}$ output neurons (with weights $\mathbf{W}_{2}\in\mathbb{R}^{m_{2}\times m_{1}}$) without activations.
The 2-layer network computes the map $\phi\colon\mathbb{R}^{d}\to\mathbb{R}$ with $\phi(\mathbf{x})\coloneqq\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},\mathbf{b}}(
\mathbf{x})$.
The formal decision problem is the following.

2-Layer ReLU-Surjectivity
Input:
matrices $\mathbf{W}_{1}\in\mathbb{R}^{m_{1}\times d},\mathbf{W}_{2}\in\mathbb{R}^{m_{2}
\times m_{1}}$, and $\mathbf{b}\in\mathbb{R}^{m_{1}}$
Question:
is $\phi$ surjective?

In this work, we only consider the case of one-dimensional output ($m_{2}=1$).
For larger output dimension, we leave a concise characterization (and containment in NP) open.
In the one-dimensional case, it is well-known that $\mathbf{W}_{2}\in\{1,-1\}^{1\times m_{1}}$ can be assumed without loss of generality.

In Section 5.1, we characterize 2-Layer ReLU-Surjectivity and show that it is polynomially equivalent to 2-Layer ReLU-Positivity, i.e., deciding whether there exists an $\mathbf{x}\in\mathbb{R}^{d}$ such that $\phi(\mathbf{x})>0$.
In Section 5.3, we prove that 2-Layer ReLU-Positivity and therefore also 2-Layer ReLU-Surjectivity are NP-complete.
Additionally, in Section 5.2, we show that this even implies NP-hardness for a very restricted case of network verification.

### 5.1 Characterization of Surjectivity

We start with some simple observations characterizing surjectivity; see Section A.1.6 for a proof.

###### Lemma 13 .

For output dimension $m_{2}=1$, the following hold:

- a)
For $\mathbf{b}=\mathbf{0}$, the map $\phi$ is surjective if and only if there exist $\mathbf{v}^{+},\mathbf{v}^{-}\in\mathbb{R}^{d}$ such that
$\phi(\mathbf{v}^{+})>0$ and $\phi(\mathbf{v}^{-})<0$.
- b)
The map $\phi$ is surjective if and only if the map $\phi_{\mathbf{0}}$ with $\phi_{\mathbf{0}}(\mathbf{x})\coloneqq\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},
\mathbf{0}}(\mathbf{x})$ is surjective.
- c)
For $\mathbf{b}=\mathbf{0}$, the map $\phi$ is surjective if and only if there exist two ray generators $\mathbf{r}^{+},\mathbf{r}^{-}$ of two rays $\rho^{+},\rho^{-}\in\Sigma_{\mathbf{W}_{1}}$ such that $\phi(\mathbf{r}^{+})>0$ and $\phi(\mathbf{r}^{-})<0$.

Lemma 13 b) implies that we can assume $\mathbf{b}=\mathbf{0}$ without loss of generality; hence, we omit $\mathbf{b}$ in the following.
Furthermore, Lemma 13 c) implies an exponential-time algorithm for 2-Layer ReLU-Surjectivity since $\Sigma_{\mathbf{W}_{1}}$ contains at most $\min\{2m_{1}^{d-1},2^{m_{1}+1}\}$ rays; that is, the problem is in XP when parameterized by $d$ and in FPT when parameterized by $m_{1}$.

###### Corollary 14 .

2-Layer ReLU-Surjectivity is solvable in $O(\min\{2m_{1}^{d-1},2^{m_{1}+1}\})$ time for $m_{2}=1$, where $S$ denotes the input size.

In fact, to decide surjectivity, it is actually enough to find one (say the positive) ray generator since it is easy to find some point $\mathbf{x}$ where $\phi$ is non-zero (we argue below that w.l.o.g. $\phi(\mathbf{x})<0$). To find $\mathbf{x}$, we choose an arbitrary full-dimensional cone and determine whether $\mathbf{W}_{C}$ is the zero map or not. In the former case, one can pick an arbitrary full-dimensional cone $C^{\prime}$ that shares a facet with $C$. Then, $\mathbf{W}_{C^{\prime}}\neq\mathbf{0}$ since the neuron defining the facet must be active in $C^{\prime}$. Hence, one finds a point $\mathbf{x}\in C^{\prime}$ with $\phi(\mathbf{x})\neq 0$. We give a more detailed proof of the following lemma in Section A.1.7.

###### Lemma 15 .

One can check in polynomial time whether $\phi=0$, and otherwise find a point $\mathbf{x}^{*}\in\mathbb{R}^{d}$ such that $\phi(\mathbf{x}^{*})\neq 0$.

Lemma 15 implies that 2-Layer ReLU-Surjectivity is polynomially equivalent to the following problem (if $\phi(\mathbf{x}^{*})>0$, then replace $\mathbf{W}_{2}$ with $-\mathbf{W}_{2}$ such that $\phi(\mathbf{x}^{*})<0$).

2-Layer ReLU-Positivity
Input:
matrices $\mathbf{W}_{1}\in\mathbb{R}^{m\times d},\mathbf{W}_{2}\in\mathbb{R}^{1\times m}$
Question:
is there an $\mathbf{x}\in\mathbb{R}^{d}$ such that $\phi(\mathbf{x})>0$?

In Section 5.3, we prove that 2-Layer ReLU-Positivity is NP-complete.

###### Lemma 13 .

###### Corollary 14 .

###### Lemma 15 .

### 5.2 Relation to Verification

It turns out that 2-Layer ReLU-Positivity is the complement of a special network verification problem.
Typically, these problems have the following form: Given a ReLU neural network $\phi\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ and polyhedra $P\subseteq\mathbb{R}^{d}$ and $Q\subseteq\mathbb{R}^{m}$, the task is to decide whether or not $\phi(P)\subseteq Q$. Katz et al. () show that this problem is coNP-hard for a single hidden layer, $P$ being the unit cube, and $m\geq d+1$.
Furthermore, Weng et al. () show that for deep ReLU neural networks with an arbitrary number of hidden layers the problem is coNP-hard even for $m=1$.
However, coNP-hardness for a single hidden layer with output dimension $m=1$ was open so far.

Now, the NP-hardness of 2-Layer ReLU-Positivity (Theorem 18) implies coNP-hardness of network verification for a single hidden layer with output dimension $m=1$ for any (full-dimensional) polyhedron $P$ (in fact, even for more general sets) and $Q=\mathbb{R}_{\leq t}$ for any $t\in\mathbb{R}$.
Thus, we obtain a much stronger hardness result for network verification.

Let $S\subseteq\mathbb{R}^{d}$ be any set containing an open set and $t\in\mathbb{R}$. We define the following problem.

2-Layer ReLU $(S,t)$-Verification
Input:
matrices $\mathbf{W}_{1}\in\mathbb{R}^{m\times d},\mathbf{W}_{2}\in\mathbb{R}^{1\times m
},\mathbf{b}_{1}\in\mathbb{R}^{m}$, and $b_{2}\in\mathbb{R}$
Question:
is $\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},\mathbf{b}_{1}}(\mathbf{x})+b_{2}\leq t$ for all $\mathbf{x}\in S$?

###### Proposition 16 .

For any $S\subseteq\mathbb{R}^{d}$ containing an open set and $t\in\mathbb{R}$ it holds that 2-Layer ReLU $(S,t)$-Verification is coNP-hard.

###### Proof.

We reduce from the complement of 2-Layer ReLU-Positivity.
Let $\mathbf{W}_{1}\in\mathbb{R}^{m\times d},\mathbf{W}_{2}\in\mathbb{R}^{1\times m}$ be an instance of 2-Layer ReLU-Positivity, $\varepsilon>0$, and $\mathbf{z}\in S$ be chosen such that $B_{\varepsilon}(\mathbf{z})\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\|\mathbf
{x}-\mathbf{z}\|_{2}<\varepsilon\}\subseteq S$.
We define $\mathbf{b}_{1}\coloneqq-\mathbf{W}_{1}\mathbf{z}$ and $b_{2}\coloneqq t$. Hence, it holds that

$$ $\phi(\mathbf{x})>0\iff\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},\mathbf{b}_{1}}( \mathbf{z}+\mathbf{x})+b_{2}>t.$ (1) $$

For the correctness, assume that there is an $\mathbf{x}\in\mathbb{R}^{d}$ such that $\phi(\mathbf{x})>0$. Then, by the positive homogeneity of $\phi$, we also have that $\phi(\mathbf{x}^{\prime})>0$ for $\mathbf{x}^{\prime}\coloneqq\frac{\varepsilon}{2}\frac{\mathbf{x}}{\|\mathbf{x
}\|}$. Furthermore, $\mathbf{z}+\mathbf{x}^{\prime}\in S$ and Equation 1 implies that $\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},\mathbf{b}_{1}}(\mathbf{z}+\mathbf{x}^
{\prime})+b_{2}>t$.

Conversely, if there is an $\mathbf{x}\in S$ such that $\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1},\mathbf{b}_{1}}(\mathbf{x})+b_{2}>t$, then Equation 1 implies that $\phi(\mathbf{x}-\mathbf{z})>0$, concluding the proof.
∎

###### Proposition 16 .

###### Proof.

### 5.3 NP-Completeness

We prove the NP-completeness of 2-Layer ReLU-Positivity in this section. As discussed in the previous section, this implies the NP-hardness of 2-Layer ReLU-Surjectivity and the coNP-hardness of 2-Layer ReLU $(S,t)$-Verification.

Our proof uses a reduction from the following problem:

Positive Cut
Input:
graph $G=(V,E)$ and weight function $w\colon E\to\mathbb{Z}$
Question:
is there a subset $S\subseteq V$ such that $w\bigl{(}E(S,V\setminus S)\bigr{)}>0$?

###### Proposition 17 .

Positive Cut is NP-complete.

In Appendix A.1.8 we provide a proof using a reduction from the NP-hard Densest Cut Problem (Bonsma et al. ()).

Now, we show the main result of this section via reduction from Positive Cut. A detailed proof of the following theorem is given in Section A.1.9.

###### Theorem 18 .

2-Layer ReLU-Positivity is NP-complete.

###### Proof sketch.

The problem is contained in NP since, by Lemma 13,
it is sufficient to identify an extreme ray $\rho$ as a certificate for positivity.
Since extreme rays lie in one-dimensional subspaces, they lie in the intersection of $d-1$ hyperplanes corresponding to rows of $\mathbf{W}_{1}$.
Hence, the $d-1$ rows of $\mathbf{W}_{1}$ that determine $\rho$ form a polynomial-time verifiable certificate.

To prove NP-hardness, we reduce from Positive Cut. Given a weighted graph $(G=(V,E),w)$ with $V=[n]$ and $|E|=m$, we define the 2-layer ReLU neural network $\phi\colon\mathbb{R}^{n}\to\mathbb{R}$ by

$$ $\phi(\mathbf{x})=\sum_{\{i,j\}\in E}w(\{i,j\})\cdot([\mathbf{x}_{i}-\mathbf{x} _{j}]_{+}+[\mathbf{x}_{j}-\mathbf{x}_{i}]_{+}).$ $$

For a subset $S\subseteq V$, let $\mathbf{r}_{S}\coloneqq\sum_{i\in S}\mathbf{e}_{i}\in\mathbb{R}^{n}$ and $\mathbf{r}_{S}^{\prime}\coloneqq-\sum_{i\in S\setminus V}\mathbf{e}_{i}\in
\mathbb{R}^{n}$. It follows easily that

$$ $\phi(\mathbf{r}_{S})=\phi(\mathbf{r}_{S}^{\prime})=\sum\limits_{\{i,j\}\in E(S ,V\setminus S)}w(\{i,j\})=w\bigl{(}E(S,V\setminus S)\bigr{)}.$ $$

We proceed by showing that every $\mathbf{x}$ is the conic combination of such $\mathbf{r}_{S}$ and $\mathbf{r}_{S}^{\prime}$. Hence, there is an $\mathbf{x}\in\mathbb{R}^{d}$ such that $\phi(\mathbf{x})>0$ if and only if there is an $S\subseteq V$ such that $\phi(\mathbf{r}_{S})=w\bigl{(}E(S,V\setminus S)\bigr{)}>0$, proving the correctness of the reduction.
∎

As discussed in Section 5.1, we immediately obtain the following corollary.

###### Corollary 19 .

2-Layer ReLU-Surjectivity is NP-complete.

Clearly, the above result implies NP-hardness for the general case where the output dimension $m_{2}$ is part of the input.
It is unclear, however, whether containment in NP also holds for larger output dimension.(^3^33We believe that the problem might be $\Pi^{\text{P}}_{2}$-complete for $m_{2}\geq 2$.)

###### Proposition 17 .

###### Theorem 18 .

###### Proof sketch.

###### Corollary 19 .

### 5.4 Zonotope Formulation

We conclude this section with an alternative formulation of 2-Layer ReLU-Positivity based on a duality of convex piecewise linear functions and polytopes.
Interestingly, this yields a close connection to zonotope problems which arise in areas such as robotics and control.

Let $\mathcal{F}_{d}$ be the set of convex piecewise linear functions from $\mathbb{R}^{d}$ to $\mathbb{R}$ and let $\mathcal{P}_{d}$ be the set of polytopes in $\mathbb{R}^{d}$.
For every $f\in\mathcal{F}_{d}$, there are $\{\mathbf{a}_{i}\in\mathbb{R}^{d}\}_{i\in I}$ such that $f(\mathbf{x})=\max_{i\in I}\{\mathbf{a}_{i}^{T}\mathbf{x}\}$ and there is a bijection $\varphi\colon\mathcal{F}_{d}\to\mathcal{P}_{d}$ given by

$$ $\varphi\bigl{(}\max_{i\in I}\{\mathbf{a}_{i}^{T}\mathbf{x}\}\bigr{)}= \operatorname{conv}{\{\mathbf{a}_{i}\mid i\in I\}}$ $$

with inverse $\varphi^{-1}\colon\mathcal{P}_{d}\to\mathcal{F}_{d}$ given by

$$ $\varphi^{-1}(P)(\mathbf{x})=\max\bigl{\{}\langle\mathbf{x},\mathbf{y}\rangle \mid\mathbf{y}\in P\bigr{\}}.$ $$

Furthermore, $\varphi$ is a semi-ring isomorphism between the semi-rings $(\mathcal{F}_{d},\max,+)$ and $(\mathcal{P}_{d},\operatorname{conv},+)$, where $+$ is either the pointwise addition or the Minkowski sum, respectively.(^4^44See, e.g., Zhang et al. () for more details on this correspondence.)
A *zonotope* is a Minkowski sum of line segments, i.e., given a matrix $\mathbf{G}\in\mathbb{R}^{n\times d}$, the corresponding zonotope is given by

$$ $Z(\mathbf{G})\coloneqq\Bigl{\{}\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{x}\in \sum\limits_{i\in[n]}\operatorname{conv}(0,\mathbf{g}_{i})\Bigr{\}}.$ $$

We now show that 2-Layer ReLU-Positivity is equivalent to deciding (non-)containment of certain zonotopes.
Given the map $\phi(\mathbf{x})=\mathbf{W}_{2}\cdot\phi_{\mathbf{W}_{1}}(\mathbf{x})$ (where $\mathbf{W}_{2}\in\{-1,1\}^{1\times m_{1}}$), we define the sets $I^{+}\coloneqq\{i\in[m_{1}]\mid(\mathbf{W}_{2})_{i}=1\}$ and $I^{-}\coloneqq[m_{1}]\setminus I^{+}$ and let $\mathbf{W}\coloneqq\mathbf{W}_{1}$.
Note that we have

$$ $\phi(\mathbf{x})=\sum_{i\in I^{+}}\max\{0,\mathbf{w}_{i}\mathbf{x}\}-\sum_{i \in I^{-}}\max\{0,\mathbf{w}_{i}\mathbf{x}\},$ $$

and therefore $\phi=\varphi^{-1}(Z^{+})-\varphi^{-1}(Z^{-})$, where
$Z^{+}\coloneqq\sum_{i\in I^{+}}\operatorname{conv}\{0,\mathbf{w}_{i}\}=Z(
\mathbf{W}_{I^{+}})$, and $Z^{-}\coloneqq\sum_{i\in I^{-}}\operatorname{conv}\{0,\mathbf{w}_{i}\}=Z(
\mathbf{W}_{I^{-}})$.
Note that $\varphi^{-1}(Z^{+})$ and $\varphi^{-1}(Z^{-})$ can only attain nonnegative values.
Therefore, there exists a $\mathbf{v}\in\mathbb{R}^{d}$ such that $\varphi^{-1}(Z^{+})(\mathbf{v})>\varphi^{-1}(Z^{-})(\mathbf{v})$ if and only if $Z^{+}\nsubseteq Z^{-}$.

Notably, Kulmburg and Althoff () already showed that Zonotope Containment (that is, the question whether $Z^{+}\subseteq Z^{-}$) is coNP-hard, which implies our NP-hardness of 2-Layer ReLU-Positivity (Theorem 18).
Nevertheless, we believe that our reduction is more accessible and direct and provides a different perspective on the computational hardness.
The question whether Zonotope Containment is fixed-parameter tractable with respect to $d$ is, to the best of our knowledge, open.

## 6 Conclusion

We initiate the complexity-theoretic study of deciding the two elementary properties injectivity and surjectivity for functions computed by ReLU networks.
We exclude polynomial-time algorithms for both problems, and prove fixed-parameter tractability for injectivity.
Moreover, we show that surjectivity is a basic network verification task and also equivalent to zonotope containment.
Thus, our results build new bridges between seemingly unrelated areas, and yield new insights into the complexity and expressiveness of ReLU neural networks.
We close with some open questions for future work:

- –
Can the running time for ReLU-layer Injectivity be improved? Or is it possible to prove a lower bound of $2^{\Omega(d\log d)}$?
- –
What is the (parameterized) complexity of deciding injectivity for a $2$-layer ReLU neural network?
- –
Is 2-Layer ReLU-Surjectivity (or equivalently Zonotope Containment) fixed-parameter tractable with respect to the dimension $d$?
- –
How can surjectivity be characterized for output dimension $m_{2}\geq 2$? What is the complexity of the decision problem?
- –
What is the complexity of bijectivity for 2-layer ReLU networks?

## Acknowledgments and Disclosure of Funding

We thank Aleksander Nikolov for providing the idea for the NP-hardness of Positive Cut. We are very grateful to Volker Kaibel for inspiring discussions that initiated this study. Moritz Grillo and Martin Skutella are supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy — The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

## Appendix A Appendix

### A.1 Proofs

#### A.1.1 Proof of Theorem 4

3-Uniform Hypergraph 2-Coloring
Input:
A 3-uniform hypergraph $H=(V,E)$, that is, $|e|=3$ for all $e\in E$.
Question:
Is there a 2-coloring of the nodes $V$ such that no hyperedge is monochromatic?

###### Proof.

We give a reduction from 3-Uniform Hypergraph 2-Coloring which is NP-hard Lovász []. Let $H=(V,E)$ be a 3-uniform hypergraph with $|V|=n$ and $|E|=m$. We construct a digraph $D=(U,A)$ as follows: For each $i\in\{0,1\}$, we define a node set $U_{i}$ with the $n+2m$ nodes

$$ $U_{i}\coloneqq\{v_{i}\mid v\in V\}\cup\bigcup_{e\in E}\{e_{i},e_{i}^{\prime}\}.$ $$

Moreover, for each node $v\in V$, we define a node set $X_{v}$ with the $2\deg(v)+2$ nodes

$$ $X_{v}\coloneqq\{x_{v},x_{v}^{\prime}\}\cup\{x_{v,e,0},x_{v,e,1}\mid e\in E,v \in e\}.$ $$

Finally, we define the node set $Q\coloneqq\{q_{e,i},q_{e,i}^{\prime}\mid e\in E,i\in\{0,1\}\}$ and let

$$ $U\coloneqq U_{0}\cup U_{1}\cup\bigcup_{v\in V}X_{v}\cup Q.$ $$

The arc set $A$ is defined as follows: For $i\in\{0,1\}$, we connect the nodes in $U_{i}$ with $2(|U_{i}|-1)$ arcs to a strongly connected path, that is, for an arbitrary ordering $b_{1},\ldots,b_{|U_{i}|}$ of the nodes in $U_{i}$, we insert the arcs $(b_{j},b_{j+1})$ and $(b_{j+1},b_{j})$ for each $j\in[|U_{i}|-1]$. Analogously, we also connect all nodes in $X_{v}$ for each $v\in V$ to a strongly connected path. Moreover, for each $v\in V$, we insert the cyclic arcs $(v_{0},x_{v})$, $(x_{v},v_{1})$, $(v_{1},x_{v}^{\prime})$, and $(x_{v}^{\prime},v_{0})$.
Finally, for each hyperedge $e=\{u,v,w\}\in E$ and each $i\in\{0,1\}$, we insert the arcs

- •
$(q_{e,i},q_{e,i}^{\prime})$ and $(q_{e,i}^{\prime},q_{e,i})$,
- •
$(x_{u,e,i},e_{i})$, $(e_{i},q_{e,i})$, $(q_{e,i},e_{i}^{\prime})$, and $(e_{i}^{\prime},x_{u,e,i})$, and
- •
$(x_{v,e,i},q_{e,i})$, $(q_{e,i},x_{w,e,i})$, $(x_{w,e,i},q_{e,i}^{\prime})$, and $(q_{e,i}^{\prime},x_{v,e,i})$.

Overall, the constructed digraph $D$ contains $O(n+m)$ many nodes and arcs.

For the correctness, assume first that there is a 2-coloring of the nodes of $H$ such that no hyperedge is monochromatic and let $V_{i}\subseteq V$ denote the set of nodes with color $i$. We construct a solution $A^{\prime}\subseteq A$ for $D$ as follows:
For each $v\in V_{0}$, $A^{\prime}$ contains the arcs $(x_{v},v_{1})$ and $(v_{1},x_{v}^{\prime})$, and for each $v\in V_{1}$, $A^{\prime}$ contains the arcs $(v_{0},x_{v})$ and $(x_{v}^{\prime},v_{0})$.
Clearly, these arcs are acyclic.
Further, consider a hyperedge $e=\{u,v,w\}\in E$. Since $e$ is not monochromatic, it follows that exactly one of its nodes is colored with one of the two colors, say 0 (the other case is analogous), and the two other nodes have color 1.
If $u$ is colored 0, then $A^{\prime}$ contains the arcs $(x_{u,e,1},e_{1})$, $(e_{1}^{\prime},x_{u,e,1})$, $(e_{0},q_{e,0})$, and $(q_{e,0},e_{0}^{\prime})$.
If $v$ has color 0 (the case where $w$ has color 0 is analogous), then $A^{\prime}$ contains the arcs $(x_{u,e,0},e_{0})$, $(e_{0}^{\prime},x_{u,e,0})$, $(x_{v,e,1},q_{e,1})$, $(q_{e,1},x_{v,e,1})$, $(x_{w,e,0},q_{e,0}^{\prime})$, and $(q_{e,0},x_{w,e,0})$.
It can easily be verified that $A^{\prime}$ is acyclic.
Moreover, $(U,A\setminus A^{\prime})$ is not weakly connected since e.g. all nodes in $X_{v}$ with $v\in V_{0}$ are disconnected from all nodes in $U_{1}$.

Conversely, assume that there is a solution $A^{\prime}\subseteq A$ for $D$. First, observe that in $D^{\prime}\coloneqq(U,A\setminus A^{\prime})$ all nodes in $U_{0}$ are weakly connected (since they are strongly connected in $D$). The same holds for $U_{1}$ and for each $X_{v}$, $v\in V$. Moreover, for each $v\in V$, the set $X_{v}$ is weakly connected to exactly one of the sets $U_{0}$ or $U_{1}$.
To see this, note that $X_{v}$ cannot be disconnected from both $U_{0}$ and $U_{1}$ due to the cycle involving the nodes $x_{v}$ and $x_{v}^{\prime}$.
It follows that also no $X_{v}$ can be weakly connected to both $U_{0}$ and $U_{1}$ since then $D^{\prime}$ would be weakly connected because also each node in $Q$ is connected to some $X_{v}$ due to its cyclic connections. Hence, we assign each node $v\in V$ the color $i\in\{0,1\}$ if and only if $X_{v}$ is weakly connected to $U_{i}$.

It remains to check that each hyperedge $e=\{u,v,w\}\in E$ is not monochromatic. Assume the contrary, that is, $X_{u}$, $X_{v}$, and $X_{w}$ are weakly connected to (wlog) $U_{0}$.
Then, by construction, also $q_{e,1}$ and $q_{e,1}^{\prime}$ are weakly connected to $U_{0}$. Since $X_{u}$ is not weakly connected to $U_{1}$ and therefore $A^{\prime}$ contains $(x_{u,e,1},e_{1})$ and $(e_{1}^{\prime},x_{u,e,1})$, it follows that $e_{1}$ is weakly connected to $q_{e,1}$, since otherwise $A^{\prime}$ would not be acyclic. Therefore, $e_{1}$ is also weakly connected to $U_{0}$, which yields a contradiction since then $D^{\prime}$ would be weakly connected.
∎

Figure: Figure 1: The encoding of one hyperege $\{u,v,w\}\in E$ in the digraph $D$. The cyclic directed paths connecting $X_{v}$ respectively $X_{w}$ with $U_{0}$ and $U_{1}$ are not drawn in order to not overload the figure.

###### Proof.

#### A.1.2 Proof of Theorem 6

###### Proof.

Containment in NP is easy: The set $I_{C}$ of a cell $C$ with $\operatorname{rank}(\mathbf{W}_{C})<d$ serves as a certificate.

For the NP-hardness, we reduce from Acyclic $2$-disconnection which is NP-hard by Theorem 4.
For a given digraph $D=(V=\{v_{1},\ldots,v_{n}\},A=\{a_{1},\ldots,a_{m}\})$, we construct the matrix $\mathbf{W}\in\mathbb{R}^{m\times(n-1)}$ as follows:
For every arc $a=(v_{i},v_{j})\in A$, we add the row vector $\mathbf{w}_{a}\in\mathbb{R}^{n-1}$ with

$$ $(\mathbf{w}_{a})_{\ell}=\begin{cases}1,&\ell=i\\ -1,&\ell=j\\ 0,&\text{ otherwise}\end{cases}.$ $$

For the correctness, assume first that there is a solution $A^{\prime}\subseteq A$ for $D$.
Let $I^{\prime}\coloneqq\{i\mid a_{i}\in A^{\prime}\}\subseteq[m]$.
We claim that there is a cell $C\in\mathcal{C}_{\mathbf{W}}$ with $I_{C}\subseteq[m]\setminus I^{\prime}$.
To see this, let $v_{\pi_{1}},v_{\pi_{2}},\ldots,v_{\pi_{n}}$ be a topological ordering of $V$ such that all arcs in $A^{\prime}$ point “from left to right”.
Such an ordering exists since $A^{\prime}$ is acyclic.
Let $\pi_{k}=n$ and let $\mathbf{x}\in\mathbb{R}^{n-1}$ be such that

$$ $\mathbf{x}_{\pi_{1}}<\cdots<\mathbf{x}_{\pi_{k-1}}<0<\mathbf{x}_{\pi_{k+1}}< \cdots<\mathbf{x}_{\pi_{n}}.$ $$

Then, no neuron $i\in I^{\prime}$ corresponding to an arc $a_{i}=(v_{j},v_{\ell})\in A^{\prime}$ is active at $\mathbf{x}$ since

$$ $\mathbf{w}_{a_{i}}\mathbf{x}=\begin{cases}\mathbf{x}_{j}-\mathbf{x}_{\ell},&j \neq n\wedge\ell\neq n\\ -\mathbf{x}_{\ell},&j=n\\ \mathbf{x}_{j},&\ell=n\end{cases}<0.$ $$

Hence, $\mathbf{x}$ is contained in some cell $C$ with $I_{C}\subseteq[m]\setminus I^{\prime}$.
Now, since $(V,A\setminus A^{\prime})$ is not weakly connected, it follows that $\operatorname{rank}(\mathbf{W}_{C})<n-1$.
To see this, note that there must be a node $v_{i}\in V$ that is not weakly connected to $v_{n}$, that is, there is no undirected path from $v_{i}$ to $v_{n}$.
If $\operatorname{rank}(\mathbf{W}_{C})=n-1$, then there exists a linear combination $\sum_{j\in I_{C}}c_{j}\mathbf{w}_{a_{j}}=\mathbf{e}_{i}$ of the $i$-th unit vector in $\mathbb{R}^{n-1}$.
But this implies the existence of an undirected path from $v_{i}$ to $v_{n}$ corresponding to some arcs in $\{a_{j}\mid c_{j}\neq 0\}$, which yields a contradiction.
To see this, note first that $(\mathbf{e}_{i})_{i}=1$ implies that $c_{j}\neq 0$ for some $j\in I_{C}$ such that $(\mathbf{w}_{a_{j}})_{i}\neq 0$.
Clearly, $a_{j}=(v_{i},v_{n})$ or $a_{j}=(v_{n},v_{i})$ is not possible.
Hence, $a_{j}$ must be an arc between $v_{i}$ and some $v_{k}\neq v_{n}$.
But then, we have $(c_{j}\mathbf{w}_{a_{j}})_{k}\neq 0$, whereas $(\mathbf{e}_{i})_{k}=0$.
Therefore, there exists another $j^{\prime}\in I_{C}$ such that $c_{j^{\prime}}\neq 0$ and $(\mathbf{w}_{a_{j^{\prime}}})\neq 0$.
Again, it is not possible that $a_{j^{\prime}}=(v_{k},v_{n})$ or $a_{j^{\prime}}=(v_{n},v_{k})$.
However, since $I_{C}$ is finite, repeating this argument yields a contradiction.

For the reverse direction, let $P\in\mathcal{C}_{\mathbf{W}}$ be a cell with $\operatorname{rank}(\mathbf{W}_{C})<n-1$.
Then, there exists a point $\mathbf{x}\in P$.
Now, let $i\in[m]\setminus I_{C}$ be a neuron corresponding to arc $a_{i}=(v_{j},v_{\ell})$ that is not active at $\mathbf{x}$.
Then, this implies that $\mathbf{x}_{j}-\mathbf{x}_{\ell}<0$ if $j<n$ and $\ell<n$.
If $j=n$, then this implies $\mathbf{x}_{\ell}>0$ and if $\ell=n$, then this implies $\mathbf{x}_{j}<0$.
Hence, $(V,A^{\prime})$ with $A^{\prime}\coloneqq\{a_{i}\mid i\in[m]\setminus I_{C}\}$ is acyclic since any cycle would lead to a contradiction.
Now, we claim that $(V,A\setminus A^{\prime})$ cannot be weakly connected.
Otherwise, there exists an undirected path from each $v_{i}$, $i\in[n-1]$ to $v_{n}$.
Let $v_{i}=v_{j_{0}},v_{j_{1}},\ldots,v_{j_{t}}=v_{n}$ be the nodes of such a path along the arcs $a_{\ell_{1}},\ldots,a_{\ell_{t}}$.
Then, there exists the linear combination $\sum_{k=1}^{t}c_{k}\mathbf{w}_{a_{\ell_{k}}}=\mathbf{e}_{i}$, where $c_{k}\coloneqq 1$ if $a_{\ell_{k}}=(v_{j_{k-1}},v_{j_{k}})$ and $c_{k}\coloneqq-1$ if $a_{\ell_{k}}=(v_{j_{k}},v_{j_{k-1}})$.
But this implies $\operatorname{rank}(\mathbf{W}_{C})=n-1$, which yields a contradiction.
∎

Figure: Figure 2: A digraph on $3$ nodes

###### Proof.

#### A.1.3 Proof of Lemma 9

###### Proof.

We use strong duality of linear programming.
To that end, let $\mathbf{A}\in\mathbb{R}^{m\times d}$ such that $C=\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{A}\mathbf{x}\geq\mathbf{0}\}$ and let $\mathbf{W}\coloneqq(\mathbf{w}_{1},\ldots,\mathbf{w}_{n})^{T}\in\mathbb{R}^{n
\times d}$.
Since $C\subseteq\bigcup\limits_{i=1}^{n}H_{\mathbf{w}_{i}}^{+}$, it follows that the set

$$ $\{\mathbf{x}\in\mathbb{R}^{d}\mid-\mathbf{W}\mathbf{x}\geq\mathbf{1},\mathbf{A }\mathbf{x}\geq\mathbf{0}\}\subseteq\{\mathbf{x}\in\mathbb{R}^{d}\mid-\mathbf{ W}\mathbf{x}>\mathbf{0},\mathbf{A}\mathbf{x}\geq\mathbf{0}\}$ $$

is empty and hence the following linear program does not admit a feasible solution.

$$ $\begin{matrix}\displaystyle\min_{\mathbf{x}}&0\\ \textrm{s.t.}&\mathbf{A}\mathbf{x}&\geq&\mathbf{0}\\ &-\mathbf{W}\mathbf{x}&\geq&\mathbf{1}\\ \end{matrix}$ $$

By strong duality, the dual linear program

$$ $\begin{matrix}\displaystyle\max_{\mathbf{y}}&\mathbf{1}^{T}\mathbf{y}\\ \textrm{s.t.}&\mathbf{z}^{T}\mathbf{A}-\mathbf{y}^{T}\mathbf{W}&=&\mathbf{0}\\ &\mathbf{y},\mathbf{z}&\geq&\mathbf{0}\\ \end{matrix}$ $$

has either no feasible solution or its objective value is unbounded. Since $\mathbf{y}=\mathbf{0}$ and $\mathbf{z}=\mathbf{0}$ yields a feasible solution, the latter is the case.
In particular, there is a ray $\rho$ of the cone $\{(\mathbf{y},\mathbf{z})\in\mathbb{R}^{n+m}\mid\mathbf{z}^{T}\mathbf{A}-
\mathbf{y}^{T}\mathbf{W}=\mathbf{0},\mathbf{y},\mathbf{z}\geq\mathbf{0}\}$ such that the objective value is unbounded on $\rho$.
The dimension of the subspace $\{(\mathbf{y},\mathbf{z})\in\mathbb{R}^{n+m}\mid\mathbf{z}^{T}\mathbf{A}-
\mathbf{y}^{T}\mathbf{W}=\mathbf{0}\}$ is at least $n+m-d$. Therefore, $\rho$ as a $1$-dimensional subspace lies in the intersection of at least $n+m-d-1$ many hyperplanes of the form $\{(\mathbf{y},\mathbf{z})\in\mathbb{R}^{n+m}\mid(\mathbf{y},\mathbf{z})_{i}=0\}$ and hence in the intersection of at least $n-d-1$ many hyperplanes of the form $\{(\mathbf{y},\mathbf{z})\in\mathbb{R}^{n+m}\mid\mathbf{y}_{i}=0\}$.
Let $B\subseteq[n]$ be the set of size at least $n-d-1$ such that $\rho\subseteq\bigcap_{i\in B}\{(\mathbf{y},\mathbf{z})\in\mathbb{R}^{n+m}\mid
\mathbf{y}_{i}=0\}$ (this can be computed in polynomial time; see, e.g., [Schrijver, , Corollary 14.1g]) and $A\coloneqq[n]\setminus B$ its complement.

It follows that $|A|\leq d+1$ and that the objective value of the following LP is still unbounded.

$$ $\begin{matrix}\displaystyle\max_{\mathbf{y}}&\mathbf{1}^{T}\mathbf{y}\\ \textrm{s.t.}&\mathbf{z}^{T}\mathbf{A}-\mathbf{y}_{A}^{T}\mathbf{W}_{A}&=& \mathbf{0}\\ &\mathbf{y},\mathbf{z}&\geq&\mathbf{0}\\ \end{matrix}$ $$

Again, by strong duality, this implies that the set

$$ $S\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid-\mathbf{W}_{A}\mathbf{x}\geq \mathbf{1},\mathbf{A}\mathbf{x}\geq\mathbf{0}\}$ $$

is empty.
Assume that the cone $\{\mathbf{x}\in\mathbb{R}^{d}\mid-\mathbf{W}_{A}\mathbf{x}>\mathbf{0},\mathbf{
A}\mathbf{x}\geq\mathbf{0}\}$ contains an element $\mathbf{x}$.
Let $k\coloneqq\min\limits_{i\in[d]}\{\left(-\mathbf{W}_{A}\mathbf{x}\right)_{i}\}$.
Then $\frac{1}{k}\cdot\mathbf{x}\in S$, which is a contradiction.
Hence, the set

$$ $\{\mathbf{x}\in\mathbb{R}^{d}\mid-\mathbf{W}_{A}\mathbf{x}>\mathbf{0},\mathbf{ A}\mathbf{x}\geq\mathbf{0}\}$ $$

is empty, which means that $C\subseteq\bigcup\limits_{i\in A}H_{\mathbf{w}_{i}}^{+}$, proving the claim.
∎

###### Proof.

#### A.1.4 Proof of Lemma 10

###### Proof.

Assume that the algorithm outputs some $\mathbf{x}\in\mathbb{R}^{d}$. If $\mathbf{x}$ was returned in Algorithm 1 or Algorithm 1, then this is clearly correct since either no cell has rank $d$ or there is a rank-0 cell.
If $\mathbf{x}$ was returned by some call of FindCell (Algorithm 2) in Algorithm 2, then
this is correct since $\operatorname{rank}(W_{\mathbf{x}})\leq\operatorname{rank}(C)<d$, where $W_{\mathbf{x}}\coloneqq\{\mathbf{w}_{i}\in W\mid\mathbf{w}_{i}^{T}\mathbf{x}
\geq 0\}$.
The second inequality holds since otherwise the algorithm would have returned “No” in Algorithm 2.
For the first inequality, we first observe the invariant that $W\setminus\operatorname{span}(C)\subseteq M\subseteq W$ holds at any time during execution of FindCell.
This is clear for the initial call of FindCell in Algorithm 1 in Algorithm 1.
Also, within FindCell the property holds after Algorithm 2 and for the recursive calls in Algorithm 2.
Now, $\operatorname{rank}(W_{\mathbf{x}})\leq\operatorname{rank}(C)$ holds since $\mathbf{m}_{i}^{T}\mathbf{x}<0$ for all $i\in[m]$ implies that $W_{\mathbf{x}}\cap M=\emptyset$, and thus, by our invariant, we have $C\subseteq W_{\mathbf{x}}\subseteq\operatorname{span}(C)$.

For the opposite direction, assume that there is an $\mathbf{x}\in\mathbb{R}^{d}$ such that $k\coloneqq\operatorname{rank}(W_{\mathbf{x}})<d$.
If $k=0$, then Algorithm 1 correctly returns some point of a rank-0 cell in Algorithm 1.
If $k>0$, then $W_{\mathbf{x}}$ contains at least one vector $\mathbf{w}_{i}$.
We claim that the call of FindCell in Algorithm 1 will correctly return some point from a cell with rank at most $k$.
To this end, we show that FindCell($C$, $M$) (Algorithm 2) returns a correct point whenever $C\subseteq W_{\mathbf{x}}$.
Clearly, if $\operatorname{rank}(C)=k$, then $\mathbf{x}$ satisfies the conditions in Algorithm 2 since $C\subseteq W_{\mathbf{x}}$, and thus $W_{\mathbf{x}}\subseteq\operatorname{span}(C)$ while $M\subseteq W\setminus\operatorname{span}(C)$ (due to Algorithm 2 and the invariant on $M$).
Hence, FindCell returns a correct point in this case.

Now consider the case $\operatorname{rank}(C)<k$.
If some point is returned in Algorithm 2, then this is correct (as already shown above).
If no point satisfies the conditions in Algorithm 2, then it holds $\{\mathbf{x}\mid\forall i\in[n]:\mathbf{c}_{i}^{T}\mathbf{x}\geq 0\}\subseteq
\bigcup_{i\in I}H^{+}_{\mathbf{m}_{i}}$ and
by Lemma 9, we can compute the set $A$ in Algorithm 2.
Note that $W_{\mathbf{x}}\cap\{\mathbf{m}_{i}\mid i\in A\}\neq\emptyset$.
Hence, for at least one of the recursive calls in Algorithm 2, it holds that $C\cup\{\mathbf{m}_{i}\}\subseteq W_{\mathbf{x}}$.
Moreover, $\operatorname{rank}(C\cup\{\mathbf{m}_{i}\})=\operatorname{rank}(C)+1$ since $\mathbf{m}_{i}\not\in\operatorname{span}(C)$ (due to Algorithm 2).
Hence, by induction, this call will return a correct point.
∎

###### Proof.

#### A.1.5 Proof of Lemma 11

###### Proof.

Let $S$ be the bit-length of $W$.
Clearly, Algorithm 1 and Algorithm 1 can be done in $\operatorname{poly}(S)$ time via linear programming. As regards the running time of FindCell, note first that the recursion depth is at most $d$ since every recursive call increases the rank of $C$ (as already discussed in the proof of Lemma 10) and the recursion terminates when rank $d$ is reached.
Moreover, each call of FindCell branches into at most $d+1$ recursive calls, that is, the search tree has size at most $(d+1)^{d}$.
Since all other computations within FindCell can be done in $\operatorname{poly}(S)$ time (using linear programming and Lemma 9), we obtain the desired running time.
∎

###### Proof.

#### A.1.6 Proof of Lemma 13

###### Proof.

a) If there is a $\mathbf{v}^{+}\in\mathbb{R}^{d}$ with $\phi(\mathbf{v}^{+})=a>0$, then for all $b\in[0,\infty)$ it holds that $\phi(\frac{b}{a}\mathbf{v}^{+})=b$ due to positive homogeneity of $\phi$ (analogously for all $b\in(-\infty,0]$ with $\mathbf{v}^{-}$). The other direction is trivial.

b)
We start with some preliminary observations.
Let $M^{+}=\{j\in[m_{1}]\mid(\mathbf{W}_{2})_{j}=1\}$ and $M^{-}=[m_{1}]\setminus M^{+}$.
Then it holds that

$$ $\phi(\mathbf{x})=\sum_{j\in M^{+}}[(\mathbf{W}_{1})_{j}\mathbf{x}+\mathbf{b}_{ j})]_{+}-\sum_{j\in M^{-}}[(\mathbf{W}_{1})_{j}\mathbf{x}+\mathbf{b}_{j})]_{+}.$ $$

Since $|[(\mathbf{W}_{1})_{j}\mathbf{x}+\mathbf{b}_{j})]_{+}-[(\mathbf{W}_{1})_{j}
\mathbf{x})]_{+}|\leq|\mathbf{b}_{j}|$, it follows that

$$ $|\phi(\mathbf{x}))-\phi_{\mathbf{0}}(\mathbf{x}))|\leq\sum_{j\in[m_{1}]}| \mathbf{b}_{j}|\eqqcolon B.$ (2) $$

Moreover, due to continuity of $\phi$ it holds that $\phi$ is surjective if and only if for every $a<b\in\mathbb{R}$ there are $a^{\prime},b^{\prime}\in\mathbb{R}$ with $a^{\prime}<a$ and $b^{\prime}>b$ such that $a^{\prime},b^{\prime}\in\phi(\mathbb{R}^{d})$.

Now, for the first direction, assume that $\phi$ is surjective.
Then there are $a<-B$ and $b>B$ such that $a,b\in\phi(\mathbb{R}^{d})$.
By Equation 2, it follows that there are $\mathbf{v}^{+}$ and $\mathbf{v}^{-}$ with $\phi_{\mathbf{0}}(\mathbf{v^{+}})>0$ and $\phi_{\mathbf{0}}(\mathbf{v}^{-})<0$, implying with a) that $\phi_{\mathbf{0}}$ is surjective.

For the converse direction, let $a<0<b$. By surjectivity of $\phi_{\mathbf{0}}$, we have that $a-2B\in\phi_{\mathbf{0}}(\mathbb{R}^{d})$ and $b+2B\in\phi_{\mathbf{0}}(\mathbb{R}^{d})$.
Hence, by Equation 2, it follows that there are $a^{\prime}<a$ and $b^{\prime}>b$ such that $a^{\prime},b^{\prime}\in\phi(\mathbb{R}^{d})$, implying surjectivity of $\phi$.

c) Follows directly from a) and 2.
∎

###### Proof.

#### A.1.7 Proof of Lemma 15

###### Proof.

We define the sets $I^{+}\coloneqq\{i\in[m_{1}]\mid(\mathbf{W}_{2})_{i}=1\}$ and $I^{-}\coloneqq[m_{1}]\setminus I^{+}$ and let $\mathbf{w}_{1},\ldots,\mathbf{w}_{m_{1}}$ be the rows of $\mathbf{W}_{1}$.

First, we can assume that for any $\mathbf{v}\in\mathbb{R}^{d}$ there is at most one $i\in[m_{1}]$ such that $\mathbf{w}_{i}\in\operatorname{pos}(\mathbf{v})\coloneqq\{\lambda\mathbf{v}
\mid\lambda\geq 0\}$. To see this, let $\mathbf{w}_{i}\in\operatorname{pos}(\mathbf{w}_{j})$ for some $i,j\in[m_{1}]$.
If $i,j\in I^{+}$, then we can simply delete the rows $\mathbf{w}_{i}$ and $\mathbf{w}_{j}$ and add a new row $\mathbf{w}_{i}+\mathbf{w}_{j}$ without changing the map $\phi$ (clearly the same works for $i,j\in I^{-}$). If $i\in I^{+}$ and $j\in I^{-}$, then we can delete the rows $\mathbf{w}_{i}$ and $\mathbf{w}_{j}$ and, if $\|\mathbf{w}_{j}\|_{2}\leq\|\mathbf{w}_{i}\|_{2}$, add a new row $\mathbf{w}_{i}-\mathbf{w}_{j}$ with output weight $1$ or add a new row $\mathbf{w}_{j}-\mathbf{w}_{i}$ with output weight $-1$ if $\|\mathbf{w}_{i}\|_{2}\leq\|\mathbf{w}_{j}\|_{2}$ without changing the map $\phi$.
Note that we can transform any matrix $\mathbf{W}_{1}$ to such a form in polynomial time.

Now, if for every row $\mathbf{w}_{j}$ there is a row $\mathbf{w}_{j^{\prime}}$ such that $\mathbf{w}_{j}=-\mathbf{w}_{j^{\prime}}$ and $(\mathbf{W}_{2})_{j}=-(\mathbf{W}_{2})_{j^{\prime}}$, it follows that $\phi$ is a linear map and hence we can easily check whether it is the zero map.
Otherwise, assume that for a row $\mathbf{w}_{j}$ there is no such row $\mathbf{w}_{j^{\prime}}$. Then $\mathbf{w}_{j}$ induces a hyperplane $H_{j}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{w}_{j}\mathbf{x}=0\}$ such that $\phi$ is not linear in every open neighborhood of any $\mathbf{x}\in H_{j}$ and hence the map $\phi$ is not linear and in particular cannot be the zero map. Thus, we can check in polynomial time whether $\phi=0$.

Now in the case of $\phi\neq 0$, let $I_{j}\coloneqq\{i\in[m_{1}]\mid\mathbf{w}_{i}\in\operatorname{span}(\mathbf{w}
_{j})\}$ and note that $|I_{j}|\leq 2$. For $i\in[m_{1}]$, we define the hyperplane $H_{i}\coloneqq\{\mathbf{x}\in\mathbb{R}^{d}\mid\mathbf{w}_{i}\mathbf{x}=0\}$. By definition, there exists an $\mathbf{x}\in H_{j}\setminus\left(\bigcup_{i\in[m_{1}]\setminus I_{j}}H_{i}\right)$.
Now, for

$$ $\varepsilon\coloneqq\min\{1,\nicefrac{{1}}{{2}}\min\limits_{i\in[m_{1}] \setminus I_{j}}\min\limits_{\mathbf{y}\in H_{i}}\|\mathbf{x}-\mathbf{y}\|_{2} >0\}$ $$

it holds that $\{\mathbf{x}+\delta\mathbf{w}_{j},\mathbf{x}-\delta\mathbf{w}_{j}\}\subset
\mathbb{R}^{d}\setminus\left(\bigcup_{i\in[m_{1}]\setminus I_{j}}H_{i}\right)$ for all $\delta\in(0,\varepsilon)$.
Let $\mathbf{x}^{\prime}\coloneqq\mathbf{x}+\varepsilon\mathbf{w}_{j}$ and $\mathbf{x}^{\prime\prime}\coloneqq\mathbf{x}-\varepsilon\mathbf{w}_{j}$ and let $I^{\prime}\coloneqq\{i\in[m_{1}]\mid\mathbf{w}_{i}\mathbf{x}^{\prime}>0\}$ and $I^{\prime\prime}\coloneqq\{i\in[m_{1}]\mid\mathbf{w}_{i}\mathbf{x}^{\prime
\prime}>0\}$.

We will argue now that either in the cell $C^{\prime}\in\Sigma_{\mathbf{W}_{1}}$ containing $\mathbf{x}^{\prime}$ or in the cell $C^{\prime\prime}\in\Sigma_{\mathbf{W}_{1}}$ containing $\mathbf{x}^{\prime\prime}$ we find the desired $\mathbf{x}^{*}$ with $\phi(\mathbf{x}^{*})\neq 0$.
Note that it is sufficient to prove that $\phi$ cannot be the zero map on $C^{\prime}$ and $C^{\prime\prime}$.
We prove this by showing that

$$ $\mathbf{W}_{2}\circ(\mathbf{W}_{1})_{C^{\prime}}-\mathbf{W}_{2}\circ(\mathbf{W }_{1})_{C^{\prime\prime}}\neq\mathbf{0}.$ $$

Note that $(I^{\prime}\cup I_{j})\setminus\{j\}=I^{\prime\prime}$.
If $I_{j}=\{j\}$, then

$$ $\left(\sum_{i\in I^{\prime}\cap I^{+}}\mathbf{w}_{i}-\sum_{i\in I^{\prime}\cap I ^{-}}\mathbf{w}_{i}\right)-\left(\sum_{i\in I^{\prime\prime}\cap I^{+}}\mathbf {w}_{i}-\sum_{i\in I^{\prime\prime}\cap I^{-}}\mathbf{w}_{i}\right)=\pm\mathbf {w}_{j}\neq\mathbf{0}.$ $$

If $I_{j}=\{j,j^{\prime}\}$, then we have $\mathbf{w}_{j^{\prime}}=-\lambda\mathbf{w}_{j}$ for some $\lambda>0$ and hence

$$ $\left(\sum_{i\in I^{\prime}\cap I^{+}}\mathbf{w}_{i}-\sum_{i\in I^{\prime}\cap I ^{-}}\mathbf{w}_{i}\right)-\left(\sum_{i\in I^{\prime\prime}\cap I^{+}}\mathbf {w}_{i}-\sum_{i\in I^{\prime\prime}\cap I^{-}}\mathbf{w}_{i}\right)=\pm\mathbf {w}_{j}\pm\mathbf{w}_{j^{\prime}}$ $$

equals $\mathbf{0}$ if and only if $\lambda=1$ and $(\mathbf{W}_{2})_{j}=-(\mathbf{W}_{2})_{j^{\prime}}$, which we assumed not to be the case.
∎

###### Proof.

#### A.1.8 Proof of Proposition 17

Densest Cut
Input:
A graph $G=(V,E)$ and $t\in\mathbb{Q}\cap[0,1]$.
Question:
Is there a subset $S\subseteq V$ such that $\frac{|E(S,V\setminus S)|}{|S|\cdot|V\setminus S|}>t$?

###### Proof.

We reduce from Densest Cut. Let $(V,E)$ be a graph and $t=\frac{a}{b}$ with $a<b\in\mathbb{N}$.
We construct the complete graph $K_{|V|}=(V,E^{\prime}\coloneqq{V\choose 2})$ with edge weights $w\colon E^{\prime}\to\mathbb{Z}$ by

$$ $w(\{i,j\})=\begin{cases}-ab&\{i,j\}\notin E\\ (b-a)b&\{i,j\}\in E\end{cases}.$ $$

Note that for any $S\subseteq V$, it holds that

$$ $\displaystyle w(E^{\prime}(S,V\setminus S))$ $\displaystyle=(b-a)b\cdot|E(S,V\setminus S)|-ab(|S|\cdot|V\setminus S|-|E(S,V \setminus S)|)$ $\displaystyle=b^{2}\cdot|E(S,V\setminus S)|-ab\cdot|S|\cdot|V\setminus S|.$ $$

Hence, we have

$$ $w(E^{\prime}(S,V\setminus S))>0\iff\frac{b^{2}\cdot|E(S,V\setminus S)|}{ab \cdot|S|\cdot|V\setminus S|}>1\iff\frac{|E(S,V\setminus S)|}{|S|\cdot|V \setminus S|}>\frac{a}{b}=t,$ $$

proving the correctness of the reduction.
∎

###### Proof.

#### A.1.9 Proof of Theorem 18

###### Proof.

The problem is contained in NP since, by Lemma 13,
it is sufficient to define a ray $\rho$ as a certificate for positivity.
Since rays are one-dimensional subspaces, they are the intersection of $d-1$ hyperplanes corresponding to rows of $\mathbf{W}_{1}$.
Hence, the $2(d-1)$ rows of $\mathbf{W}_{1}$ that determine $\rho$ form a polynomial-time verifiable certificate.

For the NP-hardness, we reduce from Positive Cut.
Given a weighted graph $(G=(V,E),w)$ with $V=[n]$ and $|E|=m$, we define the matrices $\mathbf{W}_{1}\in\mathbb{R}^{2m\times n}$ and $\mathbf{W}_{2}\in\mathbb{R}^{1\times 2m}$ as follows:
For each $e=\{i,j\}\in E$, $\mathbf{W}_{1}$ contains two rows $\mathbf{w}_{e}$ and $\mathbf{w}_{e}^{\prime}$, where

$$ $\mathbf{(}\mathbf{w}_{e})_{\ell}\coloneqq\begin{cases}1,&\ell=i\\ -1,&\ell=j\\ 0,&\text{ else}\end{cases}\text{ and }\mathbf{w}_{e}^{\prime}\coloneqq-\mathbf {w}_{e}.$ $$

The corresponding entries of $\mathbf{W}_{2}$ are set to $w(e)$.
Thus, the 2-layer ReLU neural network computes the map $\phi\colon\mathbb{R}^{n}\to\mathbb{R}$ with

$$ $\phi(\mathbf{x})=\sum_{\{i,j\}\in E}w(\{i,j\})\cdot([\mathbf{x}_{i}-\mathbf{x} _{j}]_{+}+[\mathbf{x}_{j}-\mathbf{x}_{i}]_{+}).$ $$

For the correctness, we start with some preliminary observations.
For a subset $S\subseteq V$, let $\mathbf{r}_{S}\coloneqq\sum_{i\in S}\mathbf{e}_{i}\in\mathbb{R}^{n}$ and $\mathbf{r}_{S}^{\prime}\coloneqq-\sum_{i\in S\setminus V}\mathbf{e}_{i}\in
\mathbb{R}^{n}$
and note that

$$ $[(\mathbf{r}_{S})_{i}-(\mathbf{r}_{S})_{j}]_{+}+[(\mathbf{r}_{S})_{j}-(\mathbf {r}_{S})_{i}]_{+}=\begin{cases}0,&\{i,j\}\notin E(S,V\setminus S)\\ 1,&\{i,j\}\in E(S,V\setminus S)\end{cases}$ $$

as well as

$$ $[(\mathbf{r}_{S}^{\prime})_{i}-(\mathbf{r}_{S}^{\prime})_{j}]_{+}+[(\mathbf{r} _{S}^{\prime})_{j}-(\mathbf{r}_{S}^{\prime})_{i}]_{+}=\begin{cases}0,&\{i,j\} \notin E(S,V\setminus S)\\ 1,&\{i,j\}\in E(S,V\setminus S)\end{cases}$ $$

and therefore

$$ $\phi(\mathbf{r}_{S})=\phi(\mathbf{r}_{S}^{\prime})=\sum\limits_{\{i,j\}\in E(S ,V\setminus S)}w(\{i,j\})=w(E(S,V\setminus S)).$ $$

As regards the correctness, if $(G,w)$ is a yes-instance, that is, there exists a subset $S\subseteq V$ with $w(E(S,V\setminus S))>0$, then $\phi(\mathbf{r}_{S})>0$.

Conversely, assume that there is a $\mathbf{v}\in\mathbb{R}^{d}$ with $\phi(\mathbf{v})>0$.
Let $\pi\in\mathcal{S}_{n+1}$ be a permutation such that $\mathbf{v}_{\pi(1)}\leq\mathbf{v}_{\pi(2)}\leq\cdots\leq\mathbf{v}_{\pi(n+1)}$, where $\mathbf{v}_{n+1}\coloneqq 0$.
Since all breakpoints $\mathbf{x}$ of $\phi_{\mathbf{W}_{1}}$ satisfy $\mathbf{x}_{i}=\mathbf{x}_{j}$ for some $i$ and $j$, the map $\phi_{\mathbf{W}_{1}}$ is linear within the pointed $n$-dimensional cone

$$ $C\coloneqq\{\mathbf{x}\in\mathbb{R}^{n}\mid\mathbf{x}_{\pi(1)}\leq\cdots\leq \mathbf{x}_{\pi(n+1)}\}=\bigcap_{i=1}^{n}\{\mathbf{x}\in\mathbb{R}^{n}\mid \mathbf{x}_{\pi(i)}\leq\mathbf{x}_{\pi(i+1)}\},$ $$

where again $\mathbf{x}_{n+1}\coloneqq 0$.
Hence, by linearity of the output layer and 2, the value $\phi(\mathbf{v})$ is a conical combination of the values of $\phi$ on the ray generators of the rays of $C$ and hence there is ray generator $\mathbf{r}$ of $C$ such that $\phi(\mathbf{r})>0$.
All rays of $C$ are the intersection of $C$ and $n-1$ hyperplanes of the form $\{\mathbf{x}\in\mathbb{R}^{n}\mid\mathbf{x}_{\pi(i)}=\mathbf{x}_{\pi(i+1)}\}$.
We denote these rays by

$$ $\rho_{k}\coloneqq\{\mathbf{x}\in\mathbb{R}^{n}\mid\mathbf{x}_{\pi(1)}=\cdots= \mathbf{x}_{\pi(k-1)}\leq\mathbf{x}_{\pi(k)}=\cdots=\mathbf{x}_{\pi(n+1)}\}$ $$

for $k\in[n]$.
Let $k\in[n]$ and $S=\{\pi(k),\ldots,\pi(n)\}$.
If $\pi^{-1}(n+1)<k$, then $\mathbf{r}_{S}$ generates $\rho_{k}$ and otherwise $\mathbf{r}_{S}^{\prime}$ generates $\rho_{k}$.
Since $\phi$ is positive on one of these ray generators, we can conclude that there is a $S\subseteq V$ such that $\phi(\mathbf{r}_{S})=\phi(\mathbf{r}_{S}^{\prime})>0$ which implies $w(E(S,V\setminus S))>0$.
∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. The relationship between zonotope containment and ReLU network surjectivity is intriguing but could be more accessible. Could you provide a more intuitive explanation or visualization of this connection? Could you also provide illustrative examples of injective/surjective/bijective ReLU networks?

2. Given the coNP-hardness of injectivity and verification, how should practitioners approach network design to avoid infeasibility? Are there specific heuristics or guidelines that could help manage these complexities?

3. The paper focuses on theoretical hardness but doesn’t discuss how existing heuristic or approximate verification methods could be employed in light of your results [1-3]. Could you comment on where your results might influence the development or improvement of such methods?

4. Neural network verification is a computationally demanding process and has been shown to be NP-hard even for simple neural networks with a single hidden layer [1]. Could the authors clarify the novel contributions of your coNP-hardness result compared to existing NP-hardness results. Specifically, how your result provides new insights or implications for verification techniques that weren't apparent from previous hardness results?

5. Could you provide more insight into the chosen parameterization for injectivity (in terms of input dimension) and its realistic applicability? For example, how might this approach scale in contexts where input dimensionality is inherently high, such as in image recognition (e.g., MNIST images vs. high-resolution images)?

6. Given the exponential runtime for injectivity checking based on input dimension, is there potential for further optimization or approaches for improving the algorithm's efficiency? Additionally, could you discuss any possible conjecture about the lower bounds that might limit algorithmic improvement?

[1] Katz et al. 2017, Reluplex: An efficient SMT solver for verifying deep neural networks.
[2] Zhang et al. 2018, Efficient Neural Network Robustness Certification with General Activation Functions.
[3] Singh et al. 2018, Fast and Effective Robustness Certification.
soundness: 3
strengths: This paper makes a valuable contribution to the theoretical understanding of ReLU neural networks, particularly concerning injectivity, verification, and surjectivity, by rigorously analyzing these problems’ computational complexity. Below is an assessment based on originality, quality, clarity, and significance.

**1. Originality**: The paper tackles the novel and previously open question of the computational complexity of determining injectivity in ReLU networks, establishing its coNP-completeness. This result is particularly impactful because injectivity is a fundamental property for many applications where reversible or unique mapping is essential. The authors also creatively connect network surjectivity with a zonotope containment problem, revealing links between neural network analysis and computational geometry. Additionally, the paper’s formulation of the verification problem as a coNP-hard challenge within ReLU network structure itself—independent of specific input conditions—is an insightful addition. This treatment expands our understanding of why verification is so difficult across many practical applications, which sets this work apart from prior studies focused on domain-specific hardness assumptions.

**2. Quality**: The theoretical rigor of this work is apparent, with thorough proofs supporting the coNP-completeness of injectivity and the coNP-hardness of verification. By also providing parameterized complexity results for small-dimension cases, the authors have strengthened the practical relevance of their findings. The authors appropriately cite foundational work and carefully build upon it, ensuring that their proofs are grounded in established literature while providing new contributions. However, including more experimental or empirical validations of these theoretical results (e.g., demonstrating the parameterized algorithm on real or synthetic networks) could further reinforce the paper’s quality and applicability.

**3. Clarity**: The paper is generally well-structured and organized logically, progressing through definitions, results, proofs, and implications. The separation between theoretical complexity results and parameterized algorithms is well-done, allowing readers to follow the main contributions without confusion. However, the paper is dense, and certain sections, particularly around zonotope containment and parameterized complexity, may benefit from clearer explanations or examples to improve accessibility. For instance, more intuitive descriptions or visualizations of zonotope-related results could enhance understanding for readers who may not be familiar with computational geometry.

In summary, this paper is a substantial and rigorous contribution with theoretical insights that carry practical implications. Its originality, depth of analysis, and potential influence on further research in neural network properties make it a valuable addition to the field. Improvements in clarity and empirical validation would further enhance its impact, but overall, the paper is a high-quality work that addresses foundational questions in neural network theory.
summary: This paper investigates the computational challenges and theoretical limitations associated with key properties of ReLU neural networks: injectivity, verification, and surjectivity. These properties are important for applications that rely on the reversibility and reliability of neural networks, such as generative models, inverse problems, and safety-critical systems like autonomous vehicles. These findings deepen the understanding of ReLU network behavior, particularly for applications where robustness and accuracy are critical.
weaknesses: This paper makes a significant theoretical contribution to the study of ReLU networks, but there are several areas where it could be further improved to enhance both its rigor and accessibility. Here are some specific areas for improvement:

**1. Limited Empirical Validation**: While the paper focuses on theoretical complexity results, an empirical component could improve its practical relevance. Implementing and testing the parameterized algorithm for injectivity on networks with small input dimensions or low neuron counts would provide insights into its effectiveness and limitations in real-world scenarios. Demonstrating the algorithm on a range of synthetic and small real datasets could validate the algorithm's runtime and parameter tractability claims, offering a concrete sense of its usability and performance. Additionally, practical experiments to showcase the difficulty of network verification and injectivity in deeper, multi-layer ReLU networks could help underscore the paper’s theoretical findings for readers in applied fields. An empirical analysis could reveal how these challenges scale and manifest in network training and verification processes.

**2. Limited Discussion on Practical Implications and Trade-offs**: While the paper addresses theoretical complexity boundaries, it lacks a nuanced discussion on the practical implications of these results for neural network practitioners. For example, the paper could delve into how the coNP-hardness of verification and injectivity should guide network architecture choices, especially in domains where reliability is paramount. It would be valuable to suggest actionable insights for practitioners, such as how to prioritize aspects like layer depth, dimensionality, or neuron count to balance network expressivity with computational feasibility. In the discussion of parameterized complexity results, additional analysis of where these results might realistically apply in common architectures could also be beneficial. For instance, clarifying the practical relevance of fixed-parameter tractability in applications where dimensionality is inherently high (e.g., vision tasks) would help readers understand where these findings might or might not be beneficial.

**3. Limited Exploration of Related Work in Neural Network Verification**: While the paper provides foundational complexity results, the treatment of related verification research could be expanded. There has been recent work on heuristics and approximation methods for ReLU network verification, which could provide important context here. Reviewing recent approaches to approximate verification or discussing alternative methods that offer partial or probabilistic verification could provide readers with additional avenues to explore beyond purely theoretical boundaries. Specifically, citing and discussing recent advancements in heuristic-based and constraint programming approaches to verification could frame the authors’ results within the current landscape of neural network verification tools and methods. This contextualization would help readers understand both the novelty and the limitations of purely theoretical approaches in applied contexts.

In summary, while the paper makes valuable theoretical contributions, it could benefit from empirical validation, improved accessibility of complex sections, and more thorough discussion of related work and practical implications. Addressing these weaknesses would broaden the impact and applicability of the findings, especially for audiences interested in practical neural network design and verification.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. Line 79: "hardness results is" should be "hardness results are".
2. Line 137: You didn't define the acronym "wlog" (without loss of generality), which might confuse some readers that haven't seen it before.
3. Line 147: "forms a polyhedral fan" it would help the reader to recall the definition of a polyhedral fan.
4. Line 157: Do you mean to write $\phi\_{\mathbf{W}\_i,\mathbf{b}\_i}$ instead of $\phi\_{\mathbf{W}\_{n\_i},\mathbf{b}\_{n\_i}}$? Also, it seems like you should index your projection mappings as $\pi\_{i,j} \colon \mathbb{R}^{n\_i}\to \mathbb{R}$ (projection onto coordinate $j$), instead of $\pi\_{j} \colon \mathbb{R}^{n\_i}\to \mathbb{R}$, since its domain depends on $i$.
5. Line 168: The set $\mathcal{R}$ is technically not well-defined since $\mathbf{r}\_\rho$ is not unique, although I see what you're getting at. If you can easily update things to make $\mathcal{R}$ well-defined, that would be great. (For example, would it work to take $\mathbf{r}\_\rho$ as the unique unit vector generating the ray $\rho$?)
6. Observation 3: Again, you're using terminology that may not be immediately accessible/commonplace for most ICLR readers; you should define what an "extreme ray" of a polyhedral cone is.
7. Line 176: I think that this brief recap of P, NP, NP-complete, coNP-complete, XP, and FPT is great, but that it should be included earlier in the paper, before the terms XP and FPT are used (otherwise, you might lose some readers early on in the introduction as soon as XP and FPT are mentioned). For example, can shorten these descriptions even more, so that you can squeeze them into the introduction right before line 58?
8. Line 196: Again, I suggest you define your acronym LP (linear program).
9. Proposition 4: The provided proof sketch might cause confusion, since what you're saying looks like deciding non-injectivity is polynomial time as it reduces to a linear programming feasibility problem. So, why then would determining injectivity be in coNP based on this interpretation of your proof sketch?
10. Line 223: Again, you're using terminology that might be unfamiliar to some readers, without defining it (e.g., "digraph" instead of directed graph, weakly connected, acyclic, etc.---not all ICLR readers are graph theorists).
11. Line 242: Typo ("completenss" instead of "completeness").
12. Line 384: What do you mean by the notation $w(E(S,V \setminus S)) > 0$? Are you referring to the condition that $w(e) > 0$ for all edges $e \in E$ connecting a vertex $v\in V$ to a vertex $v' \in V\setminus S$? If so, it would be great to define this for the reader, since the notation seems sort of nonstandard.
13. As a follow-up to my above question, line 404 makes it look like $w(E(S,V\setminus S))$ equals the sum of weights of all edges connecting vertices in $V$ to vertices in $V\setminus S$. In my opinion, this makes it even like likely for the reader to assume what you mean by the notation $w(E(S, V\setminus S))$.
14. Line 440: Do you mean $\mathbf{v}^+,\mathbf{v}^{-}$ instead of $\mathbf{v}^+,\mathbf{v}^+$?
soundness: 3
strengths: The paper provides some answers to deep theoretical questions surrounding the complexity of certain decision problems in the analysis of ReLU neural networks. The results in this paper are certainly of interest to the ICLR community. Interesting open problems are posed to the community, in the conclusion of the paper.
summary: This paper studies the complexity of deciding injectivity of a ReLU neural network. It is shown that the problem is coNP-complete. It is also shown that neural network verification (e.g., robustness verification) is coNP-hard, for "reasonable" sets in the input space (essentially, any set that contains a ball). Finally, it is also shown that deciding the surjectivity of a ReLU network is NP-complete. An explicit connection is drawn between deciding the existence of an input leading to a positive output under a scalar-valued 2-layer ReLU network, and the non-containment of two zonotopes. This gives rise to another explanation for the NP-hardness of determining positivity of a ReLU network.
weaknesses: I question the accessibility of this paper to the general ICLR audience. There is a lot of technical terminology used that is not defined for the general reader. The results in the main paper are all substantiated by rather imprecise proof sketches, rather than rigorous proofs. See also my Questions below.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - The claim in the conclusion to exclude polynomial-time algorithms seems to be too strong based on the analysis presented, as worst case complexity was analyzed. How does this claim compare to the results of [1,2,3,4]?
- Do the authors have an intuition how their bound relate to certification in practice? I.e. not assuming worst case networks or assuming that it is fine that certification sometimes failes / times out?
- Can the authors provide some intuition regarding the reduction to the graph problems in the main paper? 

**Minor questions**
- For Definition 2, is there a reason why you decided not to write $\phi_{W_l, b_l} \circ \cdots \circ \phi_{W_1, b_1}$ and instead spell $\phi_{W_l, b_l}$ out?
- In Line 440 pint a) - i suppose it should be $v^+, v^-$, yes?
soundness: 3
strengths: The complexity of network analysis is an important area of research. In general, universal approximation and robustness are important results and an important theoretical justification in the field. The writing and presentation is mostly clear. While many results, especially in the beginning where attributed to prior works, later results appear mostly novel. Further, intuition was provided throughout the paper.
summary: This paper states that the computational complexity of deciding infectivity for ReLU networks is coNP-complete. To prove this, they first show that $l$-layer ReLU injectivity is in coNP. They proceed then to show that it is also coNP-hard. However, they proceed to claim that for a single hidden layer, the problem is still tractable as long as the input dimensions are few. 

They then study the network verification problem and prove that the network verification is coNP-hard for a general class of input domains. To do that, the authors define the notion of *reasonable* sequence of subsets and show that the the problem of deciding if a single hidden layer ReLU network outputting scalars is strictly positive is NP complete. They then proceed to prove coNP-hardness. The authors claim that the results highlight that the hardness of network verification is intrinsic to ReLU networks rather than the input domain.
weaknesses: *A substantive assessment of the weaknesses of the paper. Focus on constructive and actionable insights on how the work could improve towards its stated goals. Be specific, avoid generic remarks. For example, if you believe the contribution lacks novelty, provide references and an explanation as evidence; if you believe experiments are insufficient, explain why and exactly what is missing, etc.*

Regarding the presentation, i encourage the authors to lighten the paper with some illustrations where appropriate. Further, it would be good, to have some intuition regarding the reduction to the graph problems in the paper. However, the biggest weakness of the paper is the missing related work. It is unclear how it relates to results on universal approximation for networks certified with convex relaxations like intervals [1,2,3,4] and specifically the hardness result presented in [2]. 

Further, the claims made in the conclusion appear too strong to me (see questions). 

Missing related work: 
1. Baader et. al. "[Universal Approximation with Certified Networks](https://openreview.net/forum?id=B1gX8kBtPr)", ICLR 2020
2. Zi et al. "[Interval universal approximation for neural networks](https://dl.acm.org/doi/abs/10.1145/3498675)", POPL 2022
3. Mirman et al. "[The Fundamental Limits of Neural Networks for Interval Certified Robustness](https://openreview.net/forum?id=fsacLLU35V)", TMLR 2022
4. Baader et. al. "[Expressivity of ReLU-Networks under Convex Relaxations](https://openreview.net/forum?id=awHTL3Hpto)", ICLR 2024

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 1
questions: See weakness. Overall, I suggest the authors at least improve the writing of their proofs, e.g., making them more intuitive and highlighting the intuition and main results instead of throwing everything at the reader. This brings bad practice to the theory field.
soundness: 2
strengths: This paper, if the proofs are correct, should be quite novel and point out the algorithmic complexity of some problems. However, due to the writing, it is impossible for me to check the proofs end to end, even as a researcher who authored many purely theoretical papers.
summary: This paper studies the complexity class of determining injectivity, surjectivity and robustness verification of ReLU networks. It proves the corresponding complexity class of each problem.
weaknesses: The first thing bothers me is the problem itself: determining the injectivity of a ReLU network. First, when the network maps 1d input to 1d output, injectivity and continuity (naturally hold for ReLU networks) implies monotonicity. Second, in high dimensions, a function mapping from $\mathbb{R}^m$ to $\mathbb{R}^d$ with $m>d$ cannot be injective. Third, if we only consider injectivity inside a compact input set, as long as at least one neuron could be dead in the network inside this input set, this ReLU layer is not injective, and the composition of the ReLU layer with any other functions cannot be injective. Based on this facts, I fail to see how the conclusion could be correct: deciding the injectivity of a mapping from $\mathbb{R}^m$ to $\mathbb{R}$ is hard. Note that deciding whether all neurons cannot be dead in a ReLU network is easy: if all neurons in previous layers are active, they are then linear, and can be collectively merged together into a single linear layer; then, applying IBP [1] on a single linear layer results in precise bounds [8], and we can easily derive whether neurons in the current considered ReLU layer are all active.

Second, the authors write about robustness verification, but other than citing Katz et al., most of the related works are nonsense. For example, Line 110 mentions that heuristic approaches for verification exist, but instead of citing many established verification algorithms, they cite some random papers that aren't important enough. For example, they should at least cite methods such as IBP [1], DeepPoly [2], DeepZ [3], general cutting planes [4], multi-neuron certification [5], etc. and libraries such as LiRPA [6] and CTBench [7]. Line 115 also cites some random papers to support that the expressivity of ReLU nets is important.

Third, the authors state that the conclusion of Katz et al. only applies to polyhedra input sets and does not generalize, which I kindly disagree with.  Just like the authors did to generalize, a well-behaved input set contains lots of polyhedra, and Katz et al. have proven that even verification in those subsets is hard. Therefore, I fail to see how their conclusions generalize the result from Katz et al.

**Reference**

[1] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models.

[2] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for
certifying neural networks.

[3] Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses.

[4] Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. General cutting planes for bound-propagation-based neural network verification.

[5] Claudio Ferrari, Mark Niklas Müller, Nikola Jovanovic, and Martin T. Vechev. Complete verification via multi-neuron relaxation guided branch-and-bound.

[6] Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond.

[7] Yuhao Mao, Stefan Balauca, Martin Vechev. CTBENCH: A Library and Benchmark for Certified Training.

[8] Yuhao Mao, Mark Niklas Mueller, Marc Fischer, and Martin Vechev. Understanding certified training with interval bound propagation.

Meta-review: The paper investigates the computational challenges and theoretical limitations associated with key properties of ReLU neural networks: injectivity, verification, and surjectivity. The authors had tried to address the reviewers' comments and suggestions. However, some reviewers still think that their concerns have not addressed properly. The reviewer pointed out that without concrete analyses or examples demonstrating the injectivity of neural networks, it is difficult to grasp the likelihood of a neural network (e.g., a random one) being injective. Unfortunately, some reviewers still do not support the acceptance of the paper. Based on the reviews and recommendations, I cannot accept the paper at the current stage. Although the paper is not accepted this time, I strongly encourage the authors to resubmit it to the next conference venue.

Decision: Reject