Solving the Closest Vector Problem with respect to Lp Norms
In this paper, we present a deterministic algorithm for the closest vector
problem for all l_p-norms, 1 < p < \infty, and all polyhedral norms, especially
for the l_1-norm and the l_{\infty}-norm. We achieve our results by introducing
a new lattice problem, the lattice membership problem. 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 for all l_p-norms, 1 < p < \infty, in time p
log_2 (r)^{O (1)} n^{(5/2+o(1))n} and for all polyhedral norms in time (s log_2
(r))^{O (1)} n^{(2+o(1))n}, where s is the number of constraints defining the
polytope and r is an upper bound on the coefficients used to describe the
convex body.