On the CVP for the root lattices via folding with deep ReLU neural networks

Vincent Corlay; Joseph J. Boutros; Philippe Ciblat; Loic Brunel

doi:10.1109/ISIT.2019.8849501

On the CVP for the root lattices via folding with deep ReLU neural networks

Vincent Corlay
, Joseph J. Boutros
, Philippe Ciblat
, Loic Brunel

Telecom Paris
Mitsubishi Electric
Texas A&M University at Qatar

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in reals ⁿ, 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 neural 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 neural network.

langue originale	Anglais
titre	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Editeur	Institute of Electrical and Electronics Engineers Inc.
Pages	1622-1626
Nombre de pages	5
ISBN (Electronique)	9781538692912
Les DOIs	https://doi.org/10.1109/ISIT.2019.8849501
état	Publié - 1 juil. 2019
Evénement	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Durée: 7 juil. 2019 → 12 juil. 2019

Série de publications

Nom	IEEE International Symposium on Information Theory - Proceedings
Volume	2019-July
ISSN (imprimé)	2157-8095

Une conférence

Une conférence	2019 IEEE International Symposium on Information Theory, ISIT 2019
Pays/Territoire	France
La ville	Paris
période	7/07/19 → 12/07/19

Accès au document

10.1109/ISIT.2019.8849501

Contient cette citation

Corlay, V., Boutros, J. J., Ciblat, P., & Brunel, L. (2019). On the CVP for the root lattices via folding with deep ReLU neural networks. Dans 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings (p. 1622-1626). Article 8849501 (IEEE International Symposium on Information Theory - Proceedings; Vol 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2019.8849501

@inproceedings{ae49307cdc694e8a9f96d261944ceb4e,

title = "On the CVP for the root lattices via folding with deep ReLU neural networks",

abstract = "Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in reals 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 neural 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 neural network.",

author = "Vincent Corlay and Boutros, \{Joseph J.\} and Philippe Ciblat and Loic Brunel",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

day = "1",

doi = "10.1109/ISIT.2019.8849501",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1622--1626",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

}

Corlay, V, Boutros, JJ, Ciblat, P & Brunel, L 2019, On the CVP for the root lattices via folding with deep ReLU neural networks. Dans 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849501, IEEE International Symposium on Information Theory - Proceedings, VOL. 2019-July, Institute of Electrical and Electronics Engineers Inc., p. 1622-1626, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849501

On the CVP for the root lattices via folding with deep ReLU neural networks. / Corlay, Vincent; Boutros, Joseph J.; Ciblat, Philippe et al.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1622-1626 8849501 (IEEE International Symposium on Information Theory - Proceedings; Vol 2019-July).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - On the CVP for the root lattices via folding with deep ReLU neural networks

AU - Corlay, Vincent

AU - Boutros, Joseph J.

AU - Ciblat, Philippe

AU - Brunel, Loic

PY - 2019/7/1

Y1 - 2019/7/1

N2 - Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in reals 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 neural 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 neural network.

AB - Point lattices and their decoding via neural networks are considered in this paper. Lattice decoding in reals 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 neural 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 neural network.

U2 - 10.1109/ISIT.2019.8849501

DO - 10.1109/ISIT.2019.8849501

M3 - Conference contribution

AN - SCOPUS:85073163010

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1622

EP - 1626

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

Corlay V, Boutros JJ, Ciblat P, Brunel L. On the CVP for the root lattices via folding with deep ReLU neural networks. Dans 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 1622-1626. 8849501. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2019.8849501

On the CVP for the root lattices via folding with deep ReLU neural networks

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation