https://hal.telecom-paris.fr/hal-02282190Corlay, VincentVincentCorlayBoutros, JosephJosephBoutrosTexas A&M University SystemCiblat, PhilippePhilippeCiblatCOMELEC - Département Communications & Electronique - Télécom ParisTechCOMNUM - Communications Numériques - LTCI - Laboratoire Traitement et Communication de l'Information - IMT - Institut Mines-Télécom [Paris] - Télécom ParisBrunel, LoïcLoïcBrunelMERCE-France - Mitsubishi Electric R&D Centre Europe [France] - Mitsubishi Electric [France]On the CVP for the root lattices via folding with deep ReLU neural networksHAL CCSD2019[MATH.MATH-IT] Mathematics [math]/Information Theory [math.IT][INFO.INFO-IT] Computer Science [cs]/Information Theory [cs.IT][INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI][INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing[STAT.AP] Statistics [stat]/Applications [stat.AP]CIBLAT, Philippe2019-09-09 18:16:332021-11-03 08:15:542019-09-10 13:24:34enConference papersapplication/pdf1Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in R n , 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.