Chandrasekaran, Karthekeyan ;
Gandikota, Venkata ;
Grigorescu, Elena
Deciding Orthogonality in ConstructionA Lattices
Abstract
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 wellknown 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 NPcomplete or in P.
In this paper, we focus on the orthogonality decision problem for a wellknown family of lattices, namely ConstructionA lattices. These are lattices of the form C + qZ^n, where C is an errorcorrecting qary 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.
BibTeX  Entry
@InProceedings{chandrasekaran_et_al:LIPIcs:2015:5650,
author = {Karthekeyan Chandrasekaran and Venkata Gandikota and Elena Grigorescu},
title = {{Deciding Orthogonality in ConstructionA Lattices}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {151162},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5650},
URN = {urn:nbn:de:0030drops56509},
doi = {10.4230/LIPIcs.FSTTCS.2015.151},
annote = {Keywords: Orthogonal Lattices, ConstructionA, Orthogonal Decomposition, Lattice isomorphism}
}
2015
Keywords: 

Orthogonal Lattices, ConstructionA, Orthogonal Decomposition, Lattice isomorphism 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

2015 