Published by the Department of Computer Science, The University of Chicago.
We provide the first hardness result for the Covering Radius Problem
on lattices (CRP). Namely, we show that for any large enough p
there exists a constant c(p) such that CRP in the
l_p norm is PI-2-hard to approximate to within any constant factor
less than c(p). In particular, for the case p=infinity, we obtain
the constant c=3/2. This gets close to the factor 2
beyond which the problem is not believed to be
PI-2-hard (Guruswami et al., Computational Complexity, 2005).
Submitted October 16, 2011, revised August 7, 2012, 2, published August 11, 2012.