Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms

Authors: Huck Bennett, Peter Ly

We study the hardness of the $γ$-approximate decisional Covering Radius Problem on lattices in the $\ell_p$ norm ($γ$-$\text{GapCRP}p$). Specifically, we prove that there is an explicit function $γ(p)$, with $γ(p) > 1$ for $p > p_0 \approx 35.31$ and $\lim{p \to \infty} γ(p) = 9/8$, such that for any constant $\varepsilon > 0$, $(γ(p) - \varepsilon)$-$\text{GapCRP}_p$ is $\mathsf{NP}$-hard. This shows the first hardness of $\text{GapCRP}p$ for explicit $p < \infty$. Work of Haviv and Regev (CCC, 2006 and CJTCS, 2012) previously showed $Π_2$-hardness of approximation for $\text{GapCRP}_p$ for all sufficiently large (but non-explicit) finite $p$ and for $p = \infty$. In fact, our hardness results hold for a variant of $\text{GapCRP}$ called the Binary Covering Radius Problem ($\text{BinGapCRP}$), which trivially reduces to both $\text{GapCRP}$ and the decisional Linear Discrepancy Problem ($\text{LinDisc}$) in any norm in an approximation-preserving way. We also show $Π_2$-hardness of $(9/8 - \varepsilon)$-$\text{BinGapCRP}$ in the $\ell_{\infty}$ norm for any constant $\varepsilon > 0$. Our work extends and heavily uses the work of Manurangsi (IPL, 2021), which showed $Π_2$-hardness of $(9/8 - \varepsilon)$-$\text{LinDisc}$ in the $\ell{\infty}$ norm.