Lattice (List) Decoding Near Minkowski's Inequality

2020/10/09 by Mook, Ethan, Peikert, Chris · 1 citation
#Data Structures and Algorithms (cs.DS) #E.4 #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2010.04809

Abstract

Minkowski proved that any n-dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most √(n); in fact, there are 2^Ω(n) such lattice vectors. Lattices whose minimum distances come close to Minkowski's bound provide excellent sphere packings and error-correcting codes in ℝⁿ. 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(√(log n)) factor of Minkowski's bound. Our primary contribution is a polynomial-time algorithm that list decodes this family to distances approaching 1/√(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.

Cited by

• List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics

Related

• List Decoding Barnes-Wall Lattices
• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
• Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
• On the decoding of lattices constructed via a single parity check
• On the decoding of Barnes-Wall lattices