Hardness of approximating the shortest vector problem in high L/sub p/ norms

摘要

We show that for every /spl epsi/ < 0, there is a constant p(/spl epsi/) such that for all integers p /spl ges/ p(/spl epsi/), it is NP-hard to approximate the shortest vector problem in L/sub p/ norm within factor p/sup 1 - /spl epsi// under randomized reductions. For large values of p, this improves the factor 2/sup 1/p/ - /spl delta/ hardness shown by D. Micciancio (1998).