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
Ravi Kumar, D. Sivakumar
ACM-SIAM 2001
Conference paper
Algorithms for ℓp low-rank approximation
Flavio Chierichetti, Sreenivas Gollapudi, et al.
ICML 2017
Conference paper
Variable Latent Semantic Indexing
Anirban Dasgupta, Prabhakar Raghavan, et al.
KDD 2005