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

CREATORHuck Bennett, Peter Ly
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79664
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.03219

Browse the full library · About the Tower of Babel