License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.46
URN: urn:nbn:de:0030-drops-68818
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6881/
Go to the corresponding LIPIcs Volume Portal

Chandrasekaran, Karthekeyan ; Cheraghchi, Mahdi ; Gandikota, Venkata ; Grigorescu, Elena

Local Testing for Membership in Lattices

pdf-format:
LIPIcs-FSTTCS-2016-46.pdf (0.5 MB)

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 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):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 from 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 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.

BibTeX - Entry

@InProceedings{chandrasekaran_et_al:LIPIcs:2016:6881,
  author =	{Karthekeyan Chandrasekaran and Mahdi Cheraghchi and Venkata Gandikota and Elena Grigorescu},
  title =	{{Local Testing for Membership in Lattices}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6881},
  URN =		{urn:nbn:de:0030-drops-68818},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.46},
  annote =	{Keywords: Lattices, Property Testing, Locally Testable Codes, Complexity Theory}
}

Keywords: Lattices, Property Testing, Locally Testable Codes, Complexity Theory
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI