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

Abstract

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).

• The article: PDF (233 Kbytes)
• Source material: ZIP (169 Kbytes)
• BibTeX entry for this article (259 bytes)

Submitted October 16, 2011, revised August 7, 2012, 2, published August 11, 2012.

© 2012 Ishay Haviv and Oded Regev
Licensed under a Creative Commons Attribution License

Volume 2012, Article 3

Volume 2012, Article 5

Volume 2012

Published articles