Approximating CVP to within almost-polynomial factors is NP-hard

I. Dinur; G. Kindler; R. Raz; S. Safra

doi:10.1007/s00493-003-0019-y

Approximating CVP to within almost-polynomial factors is NP-hard

I. Dinur, G. Kindler, R. Raz, S. Safra

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

98 Scopus citations

Abstract

This paper shows the problem of finding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor n^{c/log log n} for some constant c>0.

Original language	English (US)
Pages (from-to)	205-243
Number of pages	39
Journal	Combinatorica
Volume	23
Issue number	2
DOIs	https://doi.org/10.1007/s00493-003-0019-y
State	Published - 2003
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-003-0019-y

Cite this

@article{5911d6057e6a44f28f4995bcd79a9ace,

title = "Approximating CVP to within almost-polynomial factors is NP-hard",

abstract = "This paper shows the problem of finding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor nc/log log n for some constant c>0.",

author = "I. Dinur and G. Kindler and R. Raz and S. Safra",

year = "2003",

doi = "10.1007/s00493-003-0019-y",

language = "English (US)",

volume = "23",

pages = "205--243",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Approximating CVP to within almost-polynomial factors is NP-hard

AU - Dinur, I.

AU - Kindler, G.

AU - Raz, R.

AU - Safra, S.

PY - 2003

Y1 - 2003

N2 - This paper shows the problem of finding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor nc/log log n for some constant c>0.

AB - This paper shows the problem of finding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor nc/log log n for some constant c>0.

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

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

U2 - 10.1007/s00493-003-0019-y

DO - 10.1007/s00493-003-0019-y

M3 - Article

AN - SCOPUS:0141655066

SN - 0209-9683

VL - 23

SP - 205

EP - 243

JO - Combinatorica

JF - Combinatorica

IS - 2

ER -

Approximating CVP to within almost-polynomial factors is NP-hard

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this