Hardness of the Binary Covering Radius Problem in Large ${\ell }_p$ Norms

Abstract

We study the hardness of the ${\hat{I}}^3$-approximate decisional Covering Radius Problem on lattices in the ${\ell }_p$ norm (${\hat{I}}^3$-${\text{GapCRP}}_p$). Specifically, we prove that there is an explicit function ${\hat{I}}^3(p)$, with ${\hat{I}}^3(p)>1$ for $p>p_0\approx 35.31$ and ${\lim }_{p\to \infty }{\hat{I}}^3(p)=9/8$, such that for any constant $\epsilon >0$, $({\hat{I}}^3(p)-\epsilon )$-${\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 ${\hat{I}}_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 ${\hat{I}}_2$-hardness of $(9/8-\epsilon )$-$\text{BinGapCRP}$ in the ${\ell }_{\infty }$ norm for any constant $\epsilon >0$. Our work extends and heavily uses the work of Manurangsi (IPL, 2021), which showed ${\hat{I}}_2$-hardness of $(9/8-\epsilon )$-$\text{LinDisc}$ in the ${\ell }_{\infty }$ norm.

Minor fixes and updates from previous version