Solving the Closest Vector Problem with respect to l_p Norms

2011/04/19 by Blömer, Johannes, Naewe, Stefanie
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1104.3720

Abstract

In this paper, we present a deterministic algorithm for the closest vector problem for all l_p-norms, 1 < p < ∞, and all polyhedral norms, especially for the l₁-norm and the l_∞-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 < ∞, in time p log₂ (r)^{O (1)} n^(5/2+o(1))n and for all polyhedral norms in time (s log₂ (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.

Related

• Lattice Sparsification and the Approximate Closest Vector Problem
• Covering convex bodies and the Closest Vector Problem
• Enumerative Lattice Algorithms in Any Norm via M-Ellipsoid Coverings
• On Beating 2ⁿ for the Closest Vector Problem
• Tight Bounds for Approximate Carathéodory and Beyond