Local Testing for Membership in Lattices. Chandrasekaran, K., Cheraghchi, M., Gandikota, V., & Grigorescu, E. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 65, of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:14, 2016. Extended version in SIAM Journal on Discrete Mathematics.Link Paper doi abstract bibtex 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.
@INPROCEEDINGS{ref:conf:CCGG16,
author = {Chandrasekaran, Karthekeyan and Cheraghchi, Mahdi
and Gandikota, Venkata and Grigorescu, Elena},
title = {Local Testing for Membership in Lattices},
booktitle = {36th {IARCS Annual Conference on Foundations of
Software Technology and Theoretical Computer Science
(FSTTCS)}},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics
(LIPIcs)},
year = 2016,
volume = 65,
doi = {10.4230/LIPIcs.FSTTCS.2016.46},
note = {Extended version in {SIAM Journal on Discrete
Mathematics}.},
url_Link = {http://drops.dagstuhl.de/opus/volltexte/2016/6881},
url_Paper = {https://arxiv.org/abs/1608.00180},
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. },
keywords = {Lattices, Property Testing, Locally Testable Codes,
Complexity Theory}
}
Downloads: 0
{"_id":"Eo5fD2gPyo64J3xKD","bibbaseid":"chandrasekaran-cheraghchi-gandikota-grigorescu-localtestingformembershipinlattices-2016","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Chandrasekaran, K.","Cheraghchi, M.","Gandikota, V.","Grigorescu, E."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Chandrasekaran"],"firstnames":["Karthekeyan"],"suffixes":[]},{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]},{"propositions":[],"lastnames":["Gandikota"],"firstnames":["Venkata"],"suffixes":[]},{"propositions":[],"lastnames":["Grigorescu"],"firstnames":["Elena"],"suffixes":[]}],"title":"Local Testing for Membership in Lattices","booktitle":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","pages":"46:1–46:14","series":"Leibniz International Proceedings in Informatics (LIPIcs)","year":"2016","volume":"65","doi":"10.4230/LIPIcs.FSTTCS.2016.46","note":"Extended version in SIAM Journal on Discrete Mathematics.","url_link":"http://drops.dagstuhl.de/opus/volltexte/2016/6881","url_paper":"https://arxiv.org/abs/1608.00180","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. ","keywords":"Lattices, Property Testing, Locally Testable Codes, Complexity Theory","bibtex":"@INPROCEEDINGS{ref:conf:CCGG16,\n author =\t {Chandrasekaran, Karthekeyan and Cheraghchi, Mahdi\n and Gandikota, Venkata and Grigorescu, Elena},\n title =\t {Local Testing for Membership in Lattices},\n booktitle =\t {36th {IARCS Annual Conference on Foundations of\n Software Technology and Theoretical Computer Science\n (FSTTCS)}},\n pages =\t {46:1--46:14},\n series =\t {Leibniz International Proceedings in Informatics\n (LIPIcs)},\n year =\t 2016,\n volume =\t 65,\n doi =\t\t {10.4230/LIPIcs.FSTTCS.2016.46},\n note =\t {Extended version in {SIAM Journal on Discrete\n Mathematics}.},\n url_Link =\t {http://drops.dagstuhl.de/opus/volltexte/2016/6881},\n url_Paper =\t {https://arxiv.org/abs/1608.00180},\n abstract =\t {Testing membership in lattices is of practical\n relevance, with applications to integer programming,\n error detection in lattice-based communication, and\n cryptography. In this work, we initiate a systematic\n study of local testing for membership in lattices,\n complementing and building upon the extensive body\n of work on locally testable codes. In particular, we\n formally define the notion of local tests for\n lattices and present the following: 1. We show that\n in order to achieve low query complexity, it is\n sufficient to design $1$-sided nonadaptive canonical\n tests. This result is akin to, and based on, an\n analogous result for error-correcting codes due to\n [E. Ben-Sasson, P. Harsha, and S. Raskhodnikova,\n SIAM J. Comput., 35 (2005), pp. 1--21]. 2. We\n demonstrate upper and lower bounds on the query\n complexity of local testing for membership in code\n formula lattices. We instantiate our results for\n code formula lattices constructed from Reed--Muller\n codes to obtain nearly matching upper and lower\n bounds on the query complexity of testing such\n lattices. 3. We contrast lattice testing to code\n testing by showing lower bounds on the query\n complexity of testing low-dimensional lattices. This\n illustrates large lower bounds on the query\n complexity of testing membership in the well-known\n knapsack lattices. On the other hand, we show that\n knapsack lattices with bounded coefficients have\n low-query testers if the inputs are promised to lie\n in the span of the lattice. },\n keywords =\t {Lattices, Property Testing, Locally Testable Codes,\n Complexity Theory}\n}\n\n","author_short":["Chandrasekaran, K.","Cheraghchi, M.","Gandikota, V.","Grigorescu, E."],"key":"ref:conf:CCGG16","id":"ref:conf:CCGG16","bibbaseid":"chandrasekaran-cheraghchi-gandikota-grigorescu-localtestingformembershipinlattices-2016","role":"author","urls":{" link":"http://drops.dagstuhl.de/opus/volltexte/2016/6881"," paper":"https://arxiv.org/abs/1608.00180"},"keyword":["Lattices","Property Testing","Locally Testable Codes","Complexity Theory"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T22:14:33.013Z","downloads":0,"keywords":["lattices","property testing","locally testable codes","complexity theory"],"search_terms":["local","testing","membership","lattices","chandrasekaran","cheraghchi","gandikota","grigorescu"],"title":"Local Testing for Membership in Lattices","year":2016,"dataSources":["YZqdBBx6FeYmvQE6D"]}