PreprintCC BY 4.0arXiv
The complexity of computing the covering radius of a Euclidean lattice
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.
Related
- The Exact Second Generalized Covering Radius of Binary Primitive Triple-Error-Correcting BCH Codes
- The covering radius of RM(1,9) is precisely 242
- A sharp covering theorem and Solyanik estimates for Euclidean balls
- The Covering Radius of the Reed--Muller Code RM(1,9) is 242
- Covering radius of rank-metric codes via covering lifts and clubs
BibTeX
@misc{vallentin2026complexity,
title = {{The complexity of computing the covering radius of a Euclidean lattice}},
author = {Frank Vallentin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35027},
eprint = {2609.35027},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35027},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The complexity of computing the covering radius of a Euclidean lattice
AU - Frank Vallentin
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35027
UR - https://arxiv.org/abs/2609.35027
AB - 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.
ER -