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

Huck Bennett, Peter Ly

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…