  We characterize the complexity of the lattice decoding problem from a neural
network perspective. The notion of Voronoi-reduced basis is introduced to
restrict the space of solutions to a binary set. On the one hand, this problem
is shown to be equivalent to computing a continuous piecewise linear (CPWL)
function restricted to the fundamental parallelotope. On the other hand, it is
known that any function computed by a ReLU feed-forward neural network is CPWL.
As a result, we count the number of affine pieces in the CPWL decoding function
to characterize the complexity of the decoding problem. It is exponential in
the space dimension $n$, which induces shallow neural networks of exponential
size. For structured lattices we show that folding, a technique equivalent to
using a deep neural network, enables to reduce this complexity from exponential
in $n$ to polynomial in $n$. Regarding unstructured MIMO lattices, in contrary
to dense lattices many pieces in the CPWL decoding function can be neglected
for quasi-optimal decoding on the Gaussian channel. This makes the decoding
problem easier and it explains why shallow neural networks of reasonable size
are more efficient with this category of lattices (in low to moderate
dimensions).
