{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:29Z","timestamp":1787321069588,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1649515"],"award-info":[{"award-number":["CCF-1649515"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007289","name":"Purdue Research Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007289","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/17m1110353","type":"journal-article","created":{"date-parts":[[2018,6,7]],"date-time":"2018-06-07T10:43:40Z","timestamp":1528368220000},"page":"1265-1295","source":"Crossref","is-referenced-by-count":1,"title":["Local Testing of Lattices"],"prefix":"10.1137","volume":"32","author":[{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahdi","family":"Cheraghchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkata","family":"Gandikota","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"atypb5","first-page":"164","volume":"2014","author":"Berman P.","year":"2014","journal-title":"STOC"},{"key":"atypb6","first-page":"488","author":"Bhattacharyya A.","year":"2010","journal-title":"NV"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. Conway and N. Sloane,\n                      Sphere Packings, Lattices and Groups\n                      , 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York, 1999,https:\/\/doi.org\/10.1007\/978-1-4757-6568-7.","DOI":"10.1007\/978-1-4757-6568-7"},{"key":"atypb9","first-page":"196","author":"Eisenbrand F.","year":"2003","journal-title":"Hungary"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855591"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/18.21245"},{"key":"atypb12","unstructured":"K. Friedl and M. Sudan,\n                      Some improvements to low-degree tests\n                      , in Proceedings of the 3rd Annual Israel Symposium on Theory and Computing Systems, 1995."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2286"},{"key":"atypb14","first-page":"65","author":"Goldreich O.","year":"2010","journal-title":"Berlin"},{"key":"atypb15","first-page":"306","volume":"2005","author":"Guruswami V.","year":"2005","journal-title":"Proceedings of RANDOM\/APPROX"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Proceedings of a Symposium on the Complexity of Computer Computations, 1972, pp. 85-103,http:\/\/www.cs.berkeley.edu\/~luca\/cs172\/karp.pdf.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"atypb18","first-page":"403","volume":"2008","author":"Kaufman T.","year":"2008","journal-title":"STOC"},{"key":"atypb19","first-page":"601","author":"Kopparty S.","year":"2009","journal-title":"Berlin"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-014-9939-3"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-081-3"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055927"},{"key":"atypb24","first-page":"427","author":"Micciancio D.","year":"2009","journal-title":"Berlin"},{"key":"atypb25","unstructured":"D. Micciancio,\n                      Lecture Notes on Lattice Algorithms and Applications. Lecture 2: The Dual Lattice\n                      , 2012,https:\/\/cseweb.ucsd.edu\/classes\/wi12\/cse206A-a\/LecDual.pdf."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"D. Micciancio and S. Goldwasser,\n                      Complexity of Lattice Problems: A Cryptographic Perspective\n                      , Kluwer Internat. Ser. Engrg. Comput. Sci. 671, Kluwer Academic Publishers, Boston, MA, 2002.","DOI":"10.1007\/978-1-4615-0897-7_8"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"O. Regev,\n                      Lattice-based cryptography\n                      , in Advances in Cryptology (CRYPTO 2006), Proceedings of the 26th Annual International Cryptology Conference, Santa Barbara, CA, 2006, pp. 131-141,https:\/\/doi.org\/10.1007\/11818175_8.","DOI":"10.1007\/11818175_8"},{"key":"atypb30","first-page":"191","author":"Regev O.","year":"2010","journal-title":"Proceedings of the IEEE Conference on Computational Complexity, IEEE, Washington, DC"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb32","first-page":"279","author":"Shamir A.","year":"1983","journal-title":"Berlin"},{"key":"atypb33","unstructured":"L. A. Wolsey and G. L. Nemhauser,\n                      Integer and Combinatorial Optimization\n                      , John Wiley & Sons, New York, 2014."},{"key":"atypb34","first-page":"222","author":"Yao A.","year":"1977","journal-title":"Washington, DC"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1110353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:04Z","timestamp":1787317564000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1110353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1110353"],"URL":"https:\/\/doi.org\/10.1137\/17m1110353","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}