Lattice (List) Decoding Near Minkowski’s Inequality
Ethan Mook, Chris Peikert · IEEE Transactions on Information Theory · 2021
Minkowski proved that any$n$-dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most$\sqrt {n}$; in fact, there are$2^{\Omega (n)}$such lattice vectors. Lattices whose minimum distances come close to Minkowski’s bound provide excellent sphere packings and error-correcting codes in${\mathbb {R}}^{n}$. The focus of this work is a certain family of efficiently constructible$n$-dimensional lattices due to Barnes and Sloane, whose minimum distances are within an$O(\sqrt {\log n})$factor of Minkowski’s bound. Our primary contribution is a polynomial-time algorithm thatlist decodesthis family to distances approaching$1/\sqrt {2}$of the minimum distance. The main technique is to decode Reed-Solomon codes under error measured in the Euclidean norm, using the Koetter-Vardy “soft decision” variant of the Guruswami-Sudan list-decoding algorithm.