Solving the Closest Vector Problem with respect to $\ell_p$ Norms
Johannes Blömer, Stefanie Naewe · arXiv (Cornell University) · 2011
We present deterministic polynomially space bounded algorithms for the closest vector problem for all lp-norms, 1 < p < ∞, and all polyhedral norms, in particular for the l1norm and the l∞-norm. For all lp-norms with 1 < p < ∞ the running time of the algorithm is p · log 2 (r) O(1) n (2+o(1))n , where r is an upper bound on the size of the coefficients of the target vector and the lattice basis and n is the dimension of the vector space. For polyhedral norms, we obtain an algorithm with running time (slog 2 (r)) O(1) n (2+o(1))n , where r and n are defined as above and s is the number of constraints defining the polytope. In particular, for the l1-norm and the l∞-norm, we obtain a deterministic algorithm for the closest vector problem with running time log 2 (r) O(1) n (2+o(1))n . We achieve our results by introducing a new lattice problem, the lattice membership problem: For a given full-dimensional bounded convex set and a given lattice, the goal is to decide whether the convex set contains a lattice vector or not. The lattice membership problem is a generalization of the integer programming feasibility problem from polyhedra to bounded convex sets. In this paper, we describe a deterministic algorithm for the lattice membership problem, which is a generalization of Lenstra’s algorithm for integer programming. We also describe a polynomial time reduction from the closest vector problem to the lattice membership problem. This approach leads to a deterministic algorithm that solves the closest vector problem in polynomial space for all lp-norms, 1 < p < ∞, and all polyhedral norms.