# On the limits of non-approximability of lattice problems URL: https://dl.acm.org/doi/abs/10.1145/276698.276704 Authors: Oded Goldreich, Shafi Goldwasser ## 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.