Hardness of the Binary Covering Radius Problem in Large ℓ p \ell_{p} Norms
Huck Bennett, Peter Ly · 2026
Read Hardness of the Binary Covering Radius Problem in Large ℓ p \ell_{p} Norms by Huck Bennett, Peter Ly (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03219.txt.
Description
Huck Bennett and Peter Ly prove new hardness results for a lattice problem tied to coding and cryptography. The covering radius of a lattice is the farthest distance any point in space can sit from the lattice, and approximating it is notoriously hard. Their 2026 paper studies the problem in large p-norms, where geometry stretches toward the maximum coordinate.
They define an explicit threshold function of the norm, passing one beyond a norm of about thirty-five and rising toward nine eighths. Below that factor, the binary variant of the problem is NP-hard for every finite norm above the threshold, a first for explicit norms. In the maximum norm, the problem is even harder, complete for the second level of the polynomial hierarchy. The binary variant also transfers hardness to a classic discrepancy problem.
Catalog record
| CREATOR | Huck Bennett, Peter Ly |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79664 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03219