| Abstract |
|
We show that for every \varepsilon > 0, there is a constant p(\varepsilon) such that for all integers p \geqslant p(\varepsilon), it is NP-hard to approximate the Shortest Vector Problem in Lp norm within factor p^{1 - \varepsilon } under randomized reductions. For large values of p, this improves the factor 2^{{1 \mathord{\left/ {\vphantom {1 p}} \right. \kern-\nulldelimiterspace} p}} - \delta hardness shown by Micciancio.
|
 Additional Information
|
Citation:
Subhash Khot,
"Hardness of Approximating the Shortest Vector Problem in High Lp Norms,"
focs,
p. 290,
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
2003
|
