Approximating-CVP to within almost-polynomial factors is NP-hard
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 99-109
- https://doi.org/10.1109/sfcs.1998.743433
Abstract
This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.Keywords
This publication has 9 references indexed in Scilit:
- The hardness of approximate optima in lattices, codes, and systems of linear equationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The shortest vector in a lattice is hard to approximate to within some constantPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the limits of non-approximability of lattice problemsPublished by Association for Computing Machinery (ACM) ,1998
- A public-key cryptosystem with worst-case/average-case equivalencePublished by Association for Computing Machinery (ACM) ,1997
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latticeCombinatorica, 1990
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- On Lovász’ lattice reduction and the nearest lattice point problemCombinatorica, 1986
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971