Improved inapproximability of lattice and coding problems with preprocessing

Oded Regev

doi:10.1109/TIT.2004.833350

Improved inapproximability of lattice and coding problems with preprocessing

Oded Regev

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	2031-2037
Number of pages	7
Journal	IEEE Transactions on Information Theory
Volume	50
Issue number	9
DOIs	https://doi.org/10.1109/TIT.2004.833350
State	Published - Sep 2004

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2004.833350

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

Cite this

@article{0de22afa5dd64bce90b18fbbb3f6f418,

title = "Improved inapproximability of lattice and coding problems with preprocessing",

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

author = "Oded Regev",

year = "2004",

month = sep,

doi = "10.1109/TIT.2004.833350",

language = "English (US)",

volume = "50",

pages = "2031--2037",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - Improved inapproximability of lattice and coding problems with preprocessing

AU - Regev, Oded

PY - 2004/9

Y1 - 2004/9

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

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

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

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

U2 - 10.1109/TIT.2004.833350

DO - 10.1109/TIT.2004.833350

M3 - Article

AN - SCOPUS:4544250860

VL - 50

SP - 2031

EP - 2037

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 9

ER -