Covering convex bodies and the closest vector problem

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?

Joint work with Moritz Venzin (EPFL, Lausanne).