A sieve algorithm for the shortest lattice vector problem
2001pp. 601–610
Citations Over TimeTop 1% of 2001 papers
Abstract
We present a randomized 2^{O(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2^{O(n\log n)} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.
Related Papers
- → Distributed Broadcast in Unknown Radio Networks(2010)53 cited
- → Deterministic Resource Discovery in Distributed Networks(2003)19 cited
- → Optimal Bounds for Approximate Counting(2022)7 cited
- → Near-linear Time Dispersion of Mobile Agents(2023)1 cited
- → Distributed MIS with Low Energy and Time Complexities(2023)