Hardness of the covering radius problem on lattices

Ishay Haviv, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationProceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006
Pages145-158
Number of pages14
DOIs
StatePublished - 2006
Event21st Annual IEEE Conference on Computational Complexity, CCC 2006 - Prague, Czech Republic
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
Volume2006
ISSN (Print)1093-0159

Other

Other21st Annual IEEE Conference on Computational Complexity, CCC 2006
CountryCzech Republic
CityPrague
Period7/16/067/20/06

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Hardness of the covering radius problem on lattices'. Together they form a unique fingerprint.

Cite this