Solving the Closest Vector Problem with respect to l_p Norms

Details Solving the Closest Vector Problem with respect to l_p Norms Solving the Closest Vector Problem with respect to l_p Norms

2011-04-19

arxiv.org/abs/1104.3720v4

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Solving the Closest Vector Problem with respect to l_p Norms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving the Closest Vector Problem with respect to l_p Norms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving the Closest Vector Problem with respect to l_p Norms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183094