Improved inapproximability of lattice and coding problems with preprocessing

Research output: Contribution to journalArticle

Abstract

We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within √3-ε for any ε > 0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3 - ε. These results improve previous results of Feige and Micciancio. We also present the first inapproximability result for the relatively nearest codeword problem with preprocessing (RNCP). Finally, we describe an n-approximation algorithm to CVPP.

Original languageEnglish (US)
Pages (from-to)2031-2037
Number of pages7
JournalIEEE Transactions on Information Theory
Volume50
Issue number9
DOIs
StatePublished - Sep 2004

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Improved inapproximability of lattice and coding problems with preprocessing'. Together they form a unique fingerprint.

  • Cite this