Approximating shortest lattice vectors is not harder than approximating closest lattice vectors

• 30 July 1999
• journal article
• research article
• Published by Elsevier in Information Processing Letters
• Vol. 71  (2) , 55-61
• https://doi.org/10.1016/s0020-0190(99)00083-6

Abstract

Keywords

• COMPUTATIONAL COMPLEXITY
• COMPUTATIONAL PROBLEMS IN INTEGER LATTICES
• REDUCIBILITY AMONG APPROXIMATION PROBLEMS
• LINEAR ERROR-CORRECTING CODES
• THEORY OF COMPUTATION