Local testing for membership in lattices

DOI10.4230/LIPICS.FSTTCS.2016.46zbMATH Open1391.68121arXiv1608.00180OpenAlexW2964168370MaRDI QIDQ4636596FDOQ4636596

Venkata Gandikota, Elena Grigorescu, Mahdi Cheraghchi, Karthekeyan Chandrasekaran

Publication date: 19 April 2018

Abstract: Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in lattice-based communication, and cryptography. Apart from establishing the conceptual foundations of lattice testing, our results include the following: 1. We demonstrate upper and lower bounds on the query complexity of local testing for the well-known family of code formula lattices. Furthermore, we instantiate our results with code formula lattices constructed from Reed-Muller codes, and obtain nearly-tight bounds. 2. 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).

Full work available at URL: https://arxiv.org/abs/1608.00180

Recommendations

• Local testing of lattices
• Locally Testable Codes Require Redundant Testers
• Testing Reed–Muller Codes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Dense locally testable codes cannot have constant rate and distance

zbMATH Keywords

latticescomplexity theoryproperty testinglocally testable codes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)

Cited In (3)

• Testing equality under the local broadcast model
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• 2-transitivity is insufficient for local testability

This page was built for publication: Local testing for membership in lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636596)