Approximate ${\mathrm{CVP}}_p$ in time $2^{0.802n}$

Abstract

We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any ${\ell }_p$-norm can be computed in time $2^{(0.802+\epsilon )n}$. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. ${\ell }_2$. To obtain our result, we combine the latter algorithm w.r.t. ${\ell }_2$ with geometric insights related to coverings.

arXiv commentWe improved the introduction and added the case $p\in [1,2)$