Skip to main content
Research
SIAM Journal on Discrete Mathematics
Paper

On polynomial-factor approximations to the shortest lattice vector length

View publication

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

Conference paper

Web as a graph

R. Kumar, Prabhakar Raghavan, et al.

SIGMOD/PODS/ 2000

View all publications