Local testing for membership in lattices
File(s)
Published version
Author(s)
Chandrasekaran, K
Cheraghchi Bashi Astaneh, M
Gandikota, V
Grigorescu, E
Type
Conference Paper
Abstract
Testing membership in lattices is of practical relevance, with applications to integer program-
ming, error detection in lattice-based communication and cryptography. In this work, we initiate
a systematic study of
local testing
for membership in lattices, complementing and building upon
the extensive body of work on locally testable codes. In particular, we formally define the notion
of local tests for lattices and present the following:
1.
We show that in order to achieve low query complexity, it is sufficient to design one-sided
non-adaptive
canonical
tests. This result is akin to, and based on an analogous result for
error-correcting codes due to Ben-Sasson
et al.
(SIAM J. Computing 35(1) pp1–21).
2.
We demonstrate upper and lower bounds on the query complexity of local testing for member-
ship in
code formula
lattices. We instantiate our results for code formula lattices constructed
from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query
complexity of testing such lattices.
3.
We contrast lattice testing from code testing by showing lower bounds on the query com-
plexity of testing low-dimensional lattices. This illustrates large lower bounds on the query
complexity of testing membership in
knapsack lattices
. On the other hand, we show that
knapsack lattices with bounded coefficients have low-query testers if the inputs are promised
to lie in the span of the lattice
ming, error detection in lattice-based communication and cryptography. In this work, we initiate
a systematic study of
local testing
for membership in lattices, complementing and building upon
the extensive body of work on locally testable codes. In particular, we formally define the notion
of local tests for lattices and present the following:
1.
We show that in order to achieve low query complexity, it is sufficient to design one-sided
non-adaptive
canonical
tests. This result is akin to, and based on an analogous result for
error-correcting codes due to Ben-Sasson
et al.
(SIAM J. Computing 35(1) pp1–21).
2.
We demonstrate upper and lower bounds on the query complexity of local testing for member-
ship in
code formula
lattices. We instantiate our results for code formula lattices constructed
from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query
complexity of testing such lattices.
3.
We contrast lattice testing from code testing by showing lower bounds on the query com-
plexity of testing low-dimensional lattices. This illustrates large lower bounds on the query
complexity of testing membership in
knapsack lattices
. On the other hand, we show that
knapsack lattices with bounded coefficients have low-query testers if the inputs are promised
to lie in the span of the lattice
Date Issued
2016-12-13
Date Acceptance
2016-09-16
Citation
LIPIcs–Leibniz International Proceedings in Informatics, 2016, 23, pp.23.1-23.32
Publisher
Schloss Dagstuhl - LZI GmbH
Start Page
23.1
End Page
23.32
Journal / Book Title
LIPIcs–Leibniz International Proceedings in Informatics
Volume
23
Copyright Statement
© 2016 John Q. Open and Joan R. Access;
licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/)
licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/)
Source
Foundations of Software Technology and Theoretical Computer Science conference (FSTTCS 2016)
Publication Status
Published
Start Date
2016-12-13
Finish Date
2016-12-15
Coverage Spatial
Chennai, India