44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03) Hardness of Approximating the Shortest Vector Problem in High Lp Norms Cambridge, Massachusettes October 11-October 14 ISBN: 0-7695-2040-5
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.
Citation:
Subhash Khot, "Hardness of Approximating the Shortest Vector Problem in High Lp Norms," focs, pp.290, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb