# Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks

Vincent Froese  Technische Universität Berlin, Faculty IV, Institute of
Software Engineering and Theoretical Computer Science, Algorithmics and
Computational Complexity.
<EMAIL_ADDRESS>Moritz Grillo  Technische Universität Berlin,
Faculty II, Institute of Mathematics,
Combinatorial Optimization and Graph Algorithms.
<EMAIL_ADDRESS><EMAIL_ADDRESS>Martin Skutella
Technische Universität Berlin, Faculty II, Institute of Mathematics,
Combinatorial Optimization and Graph Algorithms.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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. (2022);
Haider et al. (2023); Furuya et al. (2023). 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. (2022); Furuya et al. (2023)
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. (2022) 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. (2022).

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.
(2018); Rössig and Petkovic (2021); Kouvaros and Lomuscio (2021); Katz et al.
(2022). 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. (2022); Weng et al. (2018). 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. (2018); Katz et al. (2022)) 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. (2022) 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 (2014)), and also known not to be
fixed-parameter tractable with respect to $d$, unless FPT = W[1] (Panolan et
al. (2015)). Haider et al. (2023) 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. (2023) 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. (2022) 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. (2018)). Several heuristic approaches exist;
see, e.g., Jordan et al. (2022); Rössig and Petkovic (2021); Kouvaros and
Lomuscio (2021).

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

##  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. (2022, 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}}$.

##### Geometry of ReLU Neural Networks.

We introduce basic definitions from polyhedral geometry; see Schrijver (1986)
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.

##### Injectivity Criterion.

Puthawala et al. (2022, 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
(1975)), 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.

##### (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 (2013) 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.,
2022, 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. (2017)). 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-Coloring111Also
known as Not-All-Equal 3-SAT. to Matching Cut by Chvátal (1984). We remark
that our reduction implies a running time lower bound based on the Exponential
Time Hypothesis222The 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 (2001)). (ETH). As discussed by Kratsch
and Le (2016), 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.

##  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.

1

Input : $W=\\{\mathbf{w}_{1},\ldots,\mathbf{w}_{m}\\}\subseteq\mathbb{R}^{d}$

Output : vector $\mathbf{x}\in\mathbb{R}^{d}$ with
$\operatorname{rank}(\\{\mathbf{w}_{i}\in
W\mid\mathbf{w}_{i}^{T}\mathbf{x}\geq 0\\})<d$ (if it exists); otherwise,
“yes”

2

3if  _$\operatorname{rank}(W) <d$,_ then return $\mathbf{0}$;

4

5if  _$\exists\mathbf{x}\in\mathbb{R}^{d}:\forall
i\in[m]:\mathbf{w}_{i}^{T}\mathbf{x} <0$,_ then return $\mathbf{x}$;

6

7$x\leftarrow$ FindCell($\emptyset$, $W$);

8 if  _$x\neq$ “no”,_ then return $x$;

return “yes”

Algorithm 1 LayerInjectivity

1

Input : vectors
$C=\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{n}\\}\subseteq\mathbb{R}^{d}$ and
$M=\\{\mathbf{m}_{1},\ldots,\mathbf{m}_{m}\\}\subseteq\mathbb{R}^{d}$

Output : vector $\mathbf{x}\in\mathbb{R}^{d}$ (if it exists) such that
$\mathbf{c}_{i}^{T}\mathbf{x}\geq 0$, for all $i\in[n]$, and
$\operatorname{rank}(C\cup\\{\mathbf{m}_{i}\mid\mathbf{m}_{i}^{T}\mathbf{x}\geq
0\\})<d$; otherwise, “no”

2 if  _$\operatorname{rank}(C)=d$ $\vee$ $\\{\mathbf{x}\mid\forall
i\in[n]:\mathbf{c}_{i}^{T}\mathbf{x}\geq 0\\}=\\{\mathbf{0}\\}$,_ then return
“no”;

3

4$I\leftarrow\bigl{\\{}i\in\\{1,\ldots,m\\}\mid\textbf{m}_{i}\notin\operatorname{span}(C)\bigr{\\}}$;

5 $M\leftarrow\\{\mathbf{m}_{i}\mid i\in I\\}$;

6

7if  _$\exists\mathbf{x}\in\mathbb{R}^{d}:\bigl{(}(\forall
i\in[n]:\mathbf{c}_{i}^{T}\mathbf{x}\geq 0)\wedge(\forall i\in
I:\mathbf{m}_{i}^{T}\mathbf{x} <0)\bigr{)}$,_ then return $\mathbf{x}$;

8

9compute $A\subseteq I$ such that $\\{\mathbf{x}\mid\forall
i\in[n]:\mathbf{c}_{i}^{T}\mathbf{x}\geq 0\\}\subseteq\bigcup_{i\in
A}H^{+}_{\mathbf{m}_{i}}$ and $|A|\leq d+1$;

10

11foreach  _$i\in A$_ do

12 $x\leftarrow$
FindCell$\left(C\cup\\{\mathbf{m}_{i}\\},M\setminus\\{\mathbf{m}_{i}\\}\right)$;

13 if  _$x\neq$ “no”,_ then return $x$;

14

15 end foreach

return “no”

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 (1923)) 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$.

##  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:

  1. 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$.

  2. 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.

  3. 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.

###  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. (2022) 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. (2018) 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. ∎

###  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. (2010)).

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.333We believe that
the problem might be $\Pi^{\text{P}}_{2}$-complete for $m_{2}\geq 2$.

###  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.444See, e.g., Zhang et al. (2018) 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 (2021) 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).

## References

  * Bonsma et al. [2010] Paul S. Bonsma, Hajo Broersma, Viresh Patel, and Artem V. Pyatkin.  The complexity status of problems related to sparsest cuts.  In _21st International Workshop on Combinatorial Algorithms (IWOCA ’10)_ , volume 6460 of _LNCS_ , pages 125–135. Springer, 2010.
  * Chvátal [1984] Vasek Chvátal.  Recognizing decomposable graphs.  _Journal of Graph Theory_ , 8(1):51–53, 1984\.
  * Downey and Fellows [2013] Rodney G. Downey and Michael R. Fellows.  _Fundamentals of Parameterized Complexity_.  Springer, 2013.
  * Figueroa et al. [2017] Ana Paulina Figueroa, César Hernández-Cruz, and Mika Olsen.  The minimum feedback arc set problem and the acyclic disconnection for graphs.  _Discrete Mathematics_ , 340(7):1514–1521, 2017\.
  * Froese and Hertrich [2023] Vincent Froese and Christoph Hertrich.  Training neural networks is NP-hard in fixed dimension.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems (NeurIPS ’23)_ , pages 44039–44049, 2023.
  * Froese et al. [2022] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier.  The computational complexity of ReLU network training parameterized by data dimensionality.  _Journal of Artificial Intelligence Research_ , 74:1775–1790, 2022.
  * Furuya et al. [2023] Takashi Furuya, Michael Puthawala, Matti Lassas, and Maarten V. de Hoop.  Globally injective and bijective neural operators.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems (NeurIPS ’23)_ , pages 57713–57753, 2023.
  * Haider et al. [2023] Daniel Haider, Martin Ehler, and Péter Balázs.  Convex geometry of ReLU-layers, injectivity on the ball and local reconstruction.  In _Proceedings of the 40th International Conference on Machine Learning (ICML ’23)_ , volume 202 of _PMLR_ , pages 12339–12350, 2023.
  * Helly [1923] Eduard Helly.  Über Mengen konvexer Körper mit gemeinschaftlichen Punkten.  _Jahresbericht der Deutschen Mathematiker-Vereinigung_ , 32:175–176, 1923.
  * Hertrich et al. [2021] Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella.  Towards lower bounds on the depth of relu neural networks.  In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS’21)_ , pages 3336–3348, 2021.
  * Impagliazzo and Paturi [2001] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of $k$-SAT.  _Journal of Computer and System Sciences_ , 62(2):367–375, 2001.
  * Jordan et al. [2022] Matt Jordan, Jonathan Hayase, Alex Dimakis, and Sewoong Oh.  Zonotope domains for Lagrangian neural network verification.  In _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems (NeurIPS’22)_ , page 8400–8413, 2022.
  * Katz et al. [2022] Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer.  Reluplex: a calculus for reasoning about deep neural networks.  _Formal Methods in System Design_ , 60(1):87–116, 2022.
  * Kouvaros and Lomuscio [2021] Panagiotis Kouvaros and Alessio Lomuscio.  Towards scalable complete verification of ReLU neural networks via dependency-based branching.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI ’21)_ , pages 2643–2650, 2021.
  * Kratsch and Le [2016] Dieter Kratsch and Van Bang Le.  Algorithms solving the matching cut problem.  _Theoretical Computer Science_ , 609:328–335, 2016.
  * Kulmburg and Althoff [2021] Adrian Kulmburg and Matthias Althoff.  On the co-NP-completeness of the zonotope containment problem.  _European Journal of Control_ , 62:84–91, 2021.
  * Lovász [1973] László Lovász.  Coverings and colorings of hypergraphs.  In _Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing_ , pages 3–12, 1973.
  * Panolan et al. [2015] Fahad Panolan, M. S. Ramanujan, and Saket Saurabh.  On the parameterized complexity of girth and connectivity problems on linear matroids.  In _Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS ’15)_ , volume 9214 of _LNCS_ , pages 566–577. Springer, 2015.
  * Puthawala et al. [2022] Michael Puthawala, Konik Kothari, Matti Lassas, Ivan Dokmanic, and Maarten V. de Hoop.  Globally injective ReLU networks.  _Journal of Machine Learning Research_ , 23:105:1–105:55, 2022.
  * Rössig and Petkovic [2021] Ansgar Rössig and Milena Petkovic.  Advances in verification of ReLU neural networks.  _Journal of Global Optimization_ , 81(1):109–152, 2021.
  * Schrijver [1986] A. Schrijver.  _Theory of Linear and Integer programming_.  Wiley-Interscience, 1986.
  * Tillmann and Pfetsch [2014] Andreas M. Tillmann and Marc E. Pfetsch.  The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing.  _IEEE Transactions on Information Theory_ , 60(2):1248–1259, 2014.
  * Weng et al. [2018] Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon.  Towards fast computation of certified robustness for ReLU networks.  In _Proceedings of the 35th International Conference on Machine Learning (ICML’18)_ , volume 80 of _PMLR_ , pages 5273–5282, 2018.
  * Zaslavsky [1975] Thomas Zaslavsky.  Facing up to arrangements: face-count formulas for partitions of space by hyperplanes.  _Memoirs of the American Mathematical Society_ , 1(154), 1975.
  * Zhang et al. [2018] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim.  Tropical geometry of deep neural networks.  In _Proceedings of the 35th International Conference on Machine Learning (ICML’18)_ , volume 80 of _PMLR_ , pages 5824–5832, 2018.

##  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 [1973]. 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. ∎

$U_{0}$$u_{0}$$v_{0}$$w_{0}$$\ldots$$e_{0}$$e_{0}^{\prime}$$\ldots$$U_{1}$$u_{1}$$v_{1}$$w_{1}$$\ldots$$e_{1}$$e_{1}^{\prime}$$\ldots$$Q_{e,0}$$Q_{e,1}$$\ldots$$X_{v}$$\ldots$$X_{u}$$\ldots$$X_{w}$
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.

####  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. ∎

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

Figure 3: The (oriented) hyperplane arrangement of the corresponding ReLU-
layer

####  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, 1986, 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. ∎

####  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. ∎

####  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. ∎

####  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. ∎

####  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. ∎

####  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. ∎

####  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$. ∎