TY - GEN
T1 - Deciding orthogonality in construction - A lattices
AU - Chandrasekaran, Karthekeyan
AU - Gandikota, Venkata
AU - Grigorescu, Elena
N1 - Publisher Copyright:
© Karthekeyan Chandrasekaran, Venkata Gandikota, and Elena Grigorescu;.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is well-known that CVP can be easily solved in lattices that have an orthogonal basis if the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form C + qZn, where C is an error-correcting q-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction- A that have an orthogonal basis. This characterization leads to an efficient algorithm solving the orthogonality decision problem, which also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem in general.
AB - Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is well-known that CVP can be easily solved in lattices that have an orthogonal basis if the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form C + qZn, where C is an error-correcting q-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction- A that have an orthogonal basis. This characterization leads to an efficient algorithm solving the orthogonality decision problem, which also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem in general.
KW - Construction-a
KW - Lattice isomorphism
KW - Orthogonal decomposition
KW - Orthogonal lattices
UR - http://www.scopus.com/inward/record.url?scp=84958776908&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958776908&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2015.151
DO - 10.4230/LIPIcs.FSTTCS.2015.151
M3 - Conference contribution
AN - SCOPUS:84958776908
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 151
EP - 162
BT - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
A2 - Harsha, Prahladh
A2 - Ramalingam, G.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
Y2 - 16 December 2015 through 18 December 2015
ER -