Аннотация:
In the closest vector problem, we are given a point in real $n$-space, and need to find the closest integer point to it according to some norm. The current fastest algorithm (Dadush and Kun, 2016) for general norms is of running time
$2^{O(n)} (1/\epsilon)^n$. We improve this substantially for certain norms, eg. for $l_p$ spaces. The result is based on a geometric covering problem that is interesting on its own. How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor 2 around their centroids, each one is contained in the $(1+\epsilon)$-scaled homothet of the ball?
