Solving the Closest Vector Problem with respect to Lp Norms

J. Blömer, S. Naewe, ArXiv:1104.3720 (2011).

Download
No fulltext has been uploaded.
Preprint | English
Abstract
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.
Publishing Year
Journal Title
arXiv:1104.3720
LibreCat-ID

Cite this

Blömer J, Naewe S. Solving the Closest Vector Problem with respect to Lp Norms. arXiv:11043720. Published online 2011.
Blömer, J., & Naewe, S. (2011). Solving the Closest Vector Problem with respect to Lp Norms. In arXiv:1104.3720.
@article{Blömer_ Naewe_2011, title={Solving the Closest Vector Problem with respect to Lp Norms}, journal={arXiv:1104.3720}, author={Blömer, Johannes and Naewe, Stefanie}, year={2011} }
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” ArXiv:1104.3720, 2011.
J. Blömer and S. Naewe, “Solving the Closest Vector Problem with respect to Lp Norms,” arXiv:1104.3720. 2011.
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” ArXiv:1104.3720, 2011.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar