# Lattice (List) Decoding Near Minkowski's Inequality

arXiv: https://arxiv.org/abs/2010.04809 · HTML: https://mlsanity.com/paper/2010.04809/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2020.

## Built on by (most cited first, 2 of 2)

- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [Property-Preserving Hashing for ℓ1-Distance Predicates: Applications to Countering Adversarial Input Attacks](https://mlsanity.com/paper/2504.16355/) (2025)

## Abstract (arXiv)

Minkowski proved that any n-dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most √n; in fact, there are 2Omega(n) such lattice vectors. Lattices whose minimum distances come close to Minkowski's bound provide excellent sphere packings and error-correcting codes in ℝ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(√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.