Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle
Chandan K. Dubey, Thomas Holenstein · arXiv (Cornell University) · 2011
We give a polynomial time Turing reduction from the $γ^2\sqrt{n}$-approximate closest vector problem on a lattice of dimension $n$ to a $γ$-approximate oracle for the shortest vector problem. This is an improvement over a reduction by Kannan, which achieved $γ^2n^{3/2}$.