Moses Charikar, Venkatesan Guruswami, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
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
Ravi Kumar, Uma Mahadevan, et al.
KDD 2004
Conference paper
Searching the workplace web
Ronald Fagin, Ravi Kumar, et al.
WWW 2003
Conference paper
On the bursty evolution of blogspace
Ravi Kumar, Jasmine Novak, et al.
WWW 2003