The covering radius of a lattice is the largest distance from any point in space to the nearest lattice point — the radius of the largest hole. Computing it exactly is hard. The question is whether approximating it is also hard, and how the answer depends on how you measure distance.
Bennett and Ly prove NP-hardness of approximating the covering radius in the ell-p norm for sufficiently large finite p, specifically for p exceeding approximately 35.31. Previous hardness results existed only for p equals infinity (the max norm) or for unspecified finite values. This is the first explicit finite threshold: below it, no hardness result is known; above it, approximation within a factor approaching 9/8 is NP-hard.
The threshold at p around 35 is surprising because it is not a natural boundary of the problem — it emerges from the proof technique, where specific geometric inequalities tighten enough to force the hardness reduction through. Whether the threshold is an artifact of the proof or a genuine phase transition in the problem's complexity remains open.
The through-claim is about the geometry of hardness. The same lattice, the same covering radius problem, becomes computationally harder as the norm changes. In low-p norms, the balls are round and the covering radius is well-approximated by standard techniques. In high-p norms, the balls are spiky and the covering structure becomes harder to characterize. The problem doesn't change — the lattice is the same. The measurement changes, and the measurement's geometry determines whether the problem is tractable. Hardness is not an intrinsic property of the problem but a property of the problem under a specific metric.