Local testing of lattices
File(s)17m1110353.pdf (508.07 KB)
Published version
Author(s)
Chandrasekaran, Karthekeyan
Cheraghchi, Mahdi
Gandikota, Venkata
Grigorescu, Elena
Type
Journal Article
Abstract
Testing membership in lattices is of practical relevance, with applications to integer programming, 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 $1$-sided nonadaptive canonical tests. This result is akin to, and based on, an analogous result for error-correcting codes due to [E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, SIAM J. Comput., 35 (2005), pp. 1--21]. 2. We demonstrate upper and lower bounds on the query complexity of local testing for membership 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 to code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in the well-known 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
2018-06-07
Date Acceptance
2018-03-27
Citation
SIAM Journal on Discrete Mathematics, 2018, 32 (2), pp.1265-1295
ISSN
0895-4801
Publisher
Society for Industrial and Applied Mathematics
Start Page
1265
End Page
1295
Journal / Book Title
SIAM Journal on Discrete Mathematics
Volume
32
Issue
2
Copyright Statement
© 2018, Society for Industrial and Applied Mathematics.
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000436975900027&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Physical Sciences
Mathematics, Applied
Mathematics
lattices
property testing
Construction-D
linear test
locally testable codes
TESTABLE CODES
APPROXIMATION
CONSTRUCTION
Publication Status
Published
Date Publish Online
2018-06-07