Locally Correctable Lattices

Abstract

Point lattices play an important role in various fields of computer science, including communication, cryptography, optimization, and machine learning. In this work, we introduce the concept of Locally Correctable Lattices (LCLs)—a class of lattices with an efficient reconstruction algorithm that can recover any index of a lattice point by querying only a small portion of a corrupted word. LCLs facilitate efficient partial decoding in the presence of noise, benefiting applications such as communication systems. We present two families of LCL constructions, each offering a range of trade-offs between lattice density, error tolerance, and the query complexity required for reconstruction.