Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
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
Ziv Bar-Yossef, T.S. Jayram, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
Conference paper
Variable Latent Semantic Indexing
Anirban Dasgupta, Prabhakar Raghavan, et al.
KDD 2005
Conference paper
Searching the workplace web
Ronald Fagin, Ravi Kumar, et al.
WWW 2003