Approximating the SVP to within a Factor (1 + 1/dim~ε) Is NP-Hard under Randomized Reductions

摘要

Recently Ajtai showed that to approximate the shortest lattice vector in the l_2-norm within a factor (1 + 2~(-dim~k)), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor (1 + dim~(-ε)), for any ε >0, is NP-hard under randomized reductions. Our proof also works for arbitrary l_p-norms, 1 ≤p < ∞.