DocumentCode
332932
Title
Approximating-CVP to within almost-polynomial factors is NP-hard
Author
Dinur, I. ; Kindler, G. ; Safra, S.
Author_Institution
Tel Aviv Univ., Israel
fYear
1998
fDate
8-11 Nov 1998
Firstpage
99
Lastpage
109
Abstract
This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2(logn)1-4 where ε=(loglogn)-c for any constant c<½
Keywords
combinatorial mathematics; computational complexity; NP-hard; almost-polynomial factors; approximating-CVP; closest vector; Cryptography; Lattices; NP-complete problem; Polynomials; Vectors;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location
Palo Alto, CA
ISSN
0272-5428
Print_ISBN
0-8186-9172-7
Type
conf
DOI
10.1109/SFCS.1998.743433
Filename
743433
Link To Document