Approximate CVP_p in time 2^0.802 n

05/11/2020

∙

by   Friedrich Eisenbrand, et al.

∙

0

∙

share

We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any ℓ_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. ℓ_2. To obtain our result, we combine the latter algorithm w.r.t. ℓ_2 with geometric insights related to coverings.