Ravi Kumar, Prabhakar Raghavan, et al.
ACM TOIT
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
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
Conference paper
On the bursty evolution of blogspace
Ravi Kumar, Jasmine Novak, et al.
WWW 2003
Ronald Fagin, Ph. Kolaitis, et al.
VLDB 2005