Tuğkan Batu, Eldar Fischer, 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
Conference paper
The predictive power of online chatter
Daniel Gruhl, R. Guha, et al.
KDD 2005
Conference paper
Approximating edit distance efficiently
Ziv Bar-Yossef, T.S. Jayram, et al.
FOCS 2004
Tuǧkan Batu, Ravi Kumar, et al.
STOC 2004