Covering Convex Bodies and the Closest Vector Problem

We present algorithms for the [Formula: see text] -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of [Formula: see text] . We improve this substantially in the following two cases. First, for [Formula: see text] -norms with [Formula: see text] (resp. [Formula: see text] ) fixed, we present an algorithm with a running time of [Formula: see text] (resp. [Formula: see text] ). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: 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 [Formula: see text] -scaled homothet of the norm ball? We provide upper bounds for this [Formula: see text] -covering number by exploiting the modulus of smoothness of the [Formula: see text] -balls. Applying a covering scheme, we can boost any 2-approximation algorithm for CVP to a [Formula: see text] -approximation algorithm with the improved run time, either using a straightforward sampling routine or using the deterministic algorithm of Dadush for the construction of an epsilon net. Second, we consider polyhedral and zonotopal norms. For centrally symmetric polytopes (resp. zonotopes) in [Formula: see text] with O(n) facets (resp. generated by O(n) line segments), we provide a deterministic [Formula: see text] time algorithm. This generalizes the result of Eisenbrand et al. which applies to the [Formula: see text] -norm. Finally, we establish a connection between the modulus of smoothness and lattice sparsification. As a consequence, using the enumeration and sparsification tools developped by Dadush, Kun, Peikert, and Vempala, we present a simple alternative to the boosting procedure with the same time and space requirement for [Formula: see text] norms. This connection might be of independent interest.