论文标题
大约$ \ mathrm {cvp} _ {p} $ in Time $ 2^{0.802 \，n} $
Approximate $\mathrm{CVP}_{p}$ in time $2^{0.802 \, n}$
论文作者
论文摘要
我们表明，最短和最接近的晶格矢量问题W.R.T.的恒定因子近似。任何$ \ ell_p $ -norm都可以按时间计算$ 2^{（0.802 +ε）\，n} $。这匹配了最短的向量问题W.R.T.当前最快的常数因子近似算法。 $ \ ell_2 $。为了获得我们的结果，我们结合了后者算法W.R.T. $ \ ell_2 $具有与封面相关的几何见解。
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 +ε)\, 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.
