preprint
Solving the Closest Vector Problem with respect to Lp Norms
Johannes
Blömer
author 23
Stefanie
Naewe
author
64
department
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.
2011
arXiv:1104.3720
J. Blömer and S. Naewe, “Solving the Closest Vector Problem with respect to Lp Norms,” <i>arXiv:1104.3720</i>. 2011.
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” <i>ArXiv:1104.3720</i>, 2011.
Blömer, J., & Naewe, S. (2011). Solving the Closest Vector Problem with respect to Lp Norms. <i>ArXiv:1104.3720</i>.
J. Blömer, S. Naewe, ArXiv:1104.3720 (2011).
@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 J, Naewe S. Solving the Closest Vector Problem with respect to Lp Norms. <i>arXiv:11043720</i>. 2011.
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” <i>ArXiv:1104.3720</i>, 2011.
29872018-06-05T07:49:32Z2022-01-06T06:58:50Z