Improved inapproximability of lattice and coding problems with preprocessing

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

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 the results of Feige and Micciancio in [10]. 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)
Title of host publicationProceedings of the Annual IEEE Conference on Computational Complexity
Pages363-370
Number of pages8
StatePublished - 2003
Event18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark
Duration: Jul 7 2003Jul 10 2003

Other

Other18th Annual IEEE Conference on Computational Complexity
CountryDenmark
CityAarhus
Period7/7/037/10/03

ASJC Scopus subject areas

  • Computational Mathematics

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

Cite this