Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
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
Alexandr Andoni, Ronald Fagin, et al.
SIGMOD 2008
Conference paper
Searching the workplace web
Ronald Fagin, Ravi Kumar, et al.
WWW 2003
Moses Charikar, Venkatesan Guruswami, et al.
Annual Symposium on Foundations of Computer Science - Proceedings