@inproceedings{9e57a9b4c18a41bd8f3a72c40e3c1850,

title = "Hardness of approximating the shortest vector problem in high Lp norms",

abstract = "We show that for every ∈ > 0, there is a constant p(∈) such that for all integers p ≥ p(∈), it is NP-hard to approximate the shortest vector problem in Lp norm within factor p1 - ∈ under randomized reductions. For large values of p, this improves the factor 21/p - δ hardness shown by D. Micciancio (1998).",

keywords = "Books, Computer science, Gaussian processes, Geometry, History, Lattices, Length measurement, Linear programming, Polynomials, Public key cryptography",

author = "S. Khot",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",

year = "2003",

doi = "10.1109/SFCS.2003.1238203",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "290--297",

booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",

}