David Liben-Nowell, Jasmine Novak, et al.
PNAS
Paper
On polynomial-factor approximations to the shortest lattice vector length
Abstract
For every constant ε > 0, we obtain a 2O(n(1/2+1/ε)) time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of n3+ε.
Related
Tuǧkan Batu, Ravi Kumar, et al.
STOC 2004
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics