ECCC-Report TR98-016https://eccc.weizmann.ac.il/report/1998/016Comments and Revisions published for TR98-016en-usMon, 30 Mar 1998 18:09:59 +0300
Paper TR98-016
| The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. |
Daniele Micciancio
https://eccc.weizmann.ac.il/report/1998/016We show that computing the approximate length of the shortest vector
in a lattice within a factor c is NP-hard for randomized reductions
for any constant c<sqrt(2). We also give a deterministic reduction
based on a number theoretic conjecture.
Mon, 30 Mar 1998 18:09:59 +0300https://eccc.weizmann.ac.il/report/1998/016