#

### 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

Israel

and

Oded Regev

Blavatnik School of Computer Science

Tel Aviv University

Israel

and

CNRS

ENS, Paris

*August 11, 2012*

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

Volume 2012, Article 3
Volume 2012, Article 5

Volume 2012
Published articles