Hardness of the Covering Radius Problem on Lattices
Ishay Haviv, Oded Regev · 2006
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 cp> 1 such that CRP in the lscrpnorm is Pi2-hard to approximate to within any constant less than cp. In particular, for the case p = infin, we obtain the constant Cinfin= 1.5. This gets close to the constant 2 beyond which the problem is not believed to be Pi2-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