Hardness of the covering radius problem on lattices

We provide the first hardness result for the covering radius problem on lattices (CRP). Namely, we show that for any large enough p les infin there exists a constant c_p > 1 such that CRP in the lscr_p norm is Pi₂-hard to approximate to within any constant less than c_p. In particular, for the case p = infin, we obtain the constant C_infin = 1.5. This gets close to the constant 2 beyond which the problem is not believed to be Pi₂-hard. As part of our proof, we establish a stronger hardness of approximation result for the forallexist-3-SAT problem with bounded occurrences. This hardness result might be useful elsewhere