The hardness of the closest vector problem with preprocessing
- 1 March 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 47 (3) , 1212-1215
- https://doi.org/10.1109/18.915688
Abstract
We give a new simple proof of the NP-hardness of the closest vector problem. In addition to being much simpler than all previously known proofs, the new proof yields new interesting results about the complexity of the closest vector problem with preprocessing. This is a variant of the closest vector problem in which the lattice is specified in advance, and can be preprocessed for an arbitrarily long amount of time before the target vector is revealed. We show that there are lattices for which the closest vector problem remains hard, regardless of the amount of preprocessing.Keywords
This publication has 21 references indexed in Scilit:
- On the complexity of decoding lattices using the Korkin-Zolotarev reduced basisIEEE Transactions on Information Theory, 1998
- Trellis complexity versus the coding gain of lattices. IIIEEE Transactions on Information Theory, 1996
- New bounds in some transference theorems in the geometry of numbersMathematische Annalen, 1993
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latticeCombinatorica, 1990
- The hardness of decoding linear codes with preprocessingIEEE Transactions on Information Theory, 1990
- Minkowski's Convex Body Theorem and Integer ProgrammingMathematics of Operations Research, 1987
- Algorithmic Geometry of NumbersAnnual Review of Computer Science, 1987
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980