Chicago Journal of Theoretical Computer Science

Volume 2012

Article 4

Published by the Department of Computer Science, The University of Chicago.

Hardness of the Covering Radius Problem on Lattices

Ishay Haviv
School of Computer Science
The Academic College of Tel Aviv-Yaffo


Oded Regev
Blavatnik School of Computer Science
Tel Aviv University
ENS, Paris

August 11, 2012


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.

DOI: 10.4086/cjtcs.2012.004

[] Volume 2012, Article 3 [] Volume 2012, Article 5
[back] Volume 2012 [back] Published articles
[CJCTS home]