Local testing for membership in lattices

DOI10.4230/LIPICS.FSTTCS.2016.46MaRDI QIDQ4636596zbMATH OpenOpenAlexFDO

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

Publication date 19 April 2018

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

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)

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

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

Cited in

(4)

• Testing equality under the local broadcast model
• Local testing of lattices
• 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)