✦ LIBER ✦
Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized Reductions
✍ Scribed by Jin-Yi Cai; Ajay Nerurkar
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 172 KB
- Volume
- 59
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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< .