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

Huck Bennett, Peter Ly

We study the hardness of the $\gamma$-approximate decisional Covering Radius Problem on lattices in the ${\ell }_p$ norm ($\gamma$-${\text{GapCRP}}_p$). Specifically, we prove that there is an ex…