On the CVP for the root lattices via folding with deep ReLU neural networks
This addresses lattice decoding in machine learning and coding theory, offering a method to reduce computational complexity for high-dimensional problems.
The paper tackles the closest vector problem (CVP) for root lattices by reformulating it as a classification problem with a piecewise linear boundary, showing that folding reduces the number of pieces from exponential to linear in dimension n. This results in a deep ReLU network requiring polynomial complexity in n, compared to an exponential requirement for a two-layer network.
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.