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 -