TY - GEN

T1 - Hardness of the covering radius problem on lattices

AU - Haviv, Ishay

AU - Regev, Oded

PY - 2006

Y1 - 2006

N2 - 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 cp > 1 such that CRP in the ℓp norm is ∏2-hard to approximate to within any constant less than c p. In particular, for the case p = ∞, we obtain the constant c∞ = 1.5. This gets close to the constant 2 beyond which the problem is not believed to be ∏2-hard. As part of our proof, we establish a stronger hardness of approximation result for the ∀∃-3-SAT problem with bounded occurrences. This hardness result might be useful elsewhere.

AB - 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 cp > 1 such that CRP in the ℓp norm is ∏2-hard to approximate to within any constant less than c p. In particular, for the case p = ∞, we obtain the constant c∞ = 1.5. This gets close to the constant 2 beyond which the problem is not believed to be ∏2-hard. As part of our proof, we establish a stronger hardness of approximation result for the ∀∃-3-SAT problem with bounded occurrences. This hardness result might be useful elsewhere.

UR - http://www.scopus.com/inward/record.url?scp=34247486199&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247486199&partnerID=8YFLogxK

U2 - 10.1109/CCC.2006.23

DO - 10.1109/CCC.2006.23

M3 - Conference contribution

AN - SCOPUS:34247486199

SN - 0769525962

SN - 9780769525969

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 145

EP - 158

BT - Proceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006

T2 - 21st Annual IEEE Conference on Computational Complexity, CCC 2006

Y2 - 16 July 2006 through 20 July 2006

ER -