Computing lattice covering radius is a complex math problem
The complexity of computing the covering radius of a Euclidean lattice
Computational Complexity
Summary
This paper shows that figuring out the covering radius of a Euclidean lattice is a very complex problem belonging to a high level in computational complexity theory. The covering radius is a measure related to how well spheres can cover all points in a lattice. The authors demonstrate that deciding this problem requires sophisticated computational resources. Additionally, the paper mentions the author's experience using generative AI to assist in mathematical research.
What this means in practice
- •For cryptography engineers: Understand limitations when designing lattice-based cryptographic systems due to the high complexity of covering radius computations.
- •For optimization software developers: Recognize that efficient algorithms for covering radius calculations are unlikely, guiding choice of approximation methods in lattice problems.
A theory result. No direct application yet.
Authors
Frank Vallentin
Abstract
In this note, we prove that the covering radius problem for Euclidean lattices is complete for the second level of the polynomial hierarchy. The note also documents the author's first experiment with generative AI as a tool for mathematical research.