[GG00] On the limits of non-approximability of lattice problems

Authors: Oded Goldreich, Shafi Goldwasser | Venue: STOC 1998, JACM 2000 | Source

Abstract

We study the limits of non-approximability of lattice problems. We show that the shortest vector problem (SVP) and the closest vector problem (CVP) are not approximable to within a factor of $n^{1/\log \log n}$ in random polynomial time, unless NP is contained in RTIME\Big($2^{\text{poly}(\log n)}$\Big). We also show that, under the same assumption, no polynomial time algorithm can approximate SVP to within any constant factor, even if randomization is allowed. Our techniques combine ideas from Ajtai’s worst-case/average-case reduction for SVP with recent results on the inapproximability of other optimization problems.