On the CVP for the root lattices via folding with deep ReLU neural
  networks
  Point lattices and their decoding via neural networks are considered in this
paper. Lattice decoding in Rn, known as the closest vector problem (CVP),
becomes a classification problem in the fundamental parallelotope with a
piecewise linear function defining the boundary. Theoretical results are
obtained by studying root lattices. We show how the number of pieces in the
boundary function reduces dramatically with folding, from exponential to
linear. This translates into a two-layer ReLU network requiring a number of
neurons growing exponentially in n to solve the CVP, whereas this complexity
becomes polynomial in n for a deep ReLU network.
