The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (6) , 2008-2035
- https://doi.org/10.1137/s0097539700373039
Abstract
No abstract availableThis publication has 18 references indexed in Scilit:
- On the Limits of Nonapproximability of Lattice ProblemsJournal of Computer and System Sciences, 2000
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectorsInformation Processing Letters, 1999
- Small Solutions to Polynomial Equations, and Low Exponent RSA VulnerabilitiesJournal of Cryptology, 1997
- The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear EquationsJournal of Computer and System Sciences, 1997
- New bounds in some transference theorems in the geometry of numbersMathematische Annalen, 1993
- Improved low-density subset sum algorithmscomputational complexity, 1992
- Solving Simultaneous Modular Equations of Low DegreeSIAM Journal on Computing, 1988
- Reconstructing Truncated Integer Variables Satisfying Linear CongruencesSIAM Journal on Computing, 1988
- On the Lagarias-Odlyzko Algorithm for the Subset Sum ProblemSIAM Journal on Computing, 1986
- On Lovász’ lattice reduction and the nearest lattice point problemCombinatorica, 1986