Shuchi Chawla, Robert Krauthgamer, et al.
Computational Complexity
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
Conference paper
Propagation of trust and distrust
R. Guha, Prabhakar Raghavan, et al.
WWW 2004
Ravi Kumar, Uma Mahadevan, et al.
KDD 2004
Conference paper
Discovering large dense subgraphs in massive graphs
David Gibson, Ravi Kumar, et al.
VLDB 2005