  This paper studies the expressive power of artificial neural networks with
rectified linear units. In order to study them as a model of real-valued
computation, we introduce the concept of Max-Affine Arithmetic Programs and
show equivalence between them and neural networks concerning natural complexity
measures. We then use this result to show that two fundamental combinatorial
optimization problems can be solved with polynomial-size neural networks.
First, we show that for any undirected graph with $n$ nodes, there is a neural
network (with fixed weights and biases) of size $\mathcal{O}(n^3)$ that takes
the edge weights as input and computes the value of a minimum spanning tree of
the graph. Second, we show that for any directed graph with $n$ nodes and $m$
arcs, there is a neural network of size $\mathcal{O}(m^2n^2)$ that takes the
arc capacities as input and computes a maximum flow. Our results imply that
these two problems can be solved with strongly polynomial time algorithms that
solely use affine transformations and maxima computations, but no
comparison-based branchings.
