---
_id: '2987'
abstract:
- lang: eng
text: "In this paper, we present a deterministic algorithm for the closest vector\r\nproblem
for all l_p-norms, 1 < p < \\infty, and all polyhedral norms, especially\r\nfor
the l_1-norm and the l_{\\infty}-norm. We achieve our results by introducing\r\na
new lattice problem, the lattice membership problem. We describe a\r\ndeterministic
algorithm for the lattice membership problem, which is a\r\ngeneralization of
Lenstra's algorithm for integer programming. We also describe\r\na polynomial
time reduction from the closest vector problem to the lattice\r\nmembership problem.
This approach leads to a deterministic algorithm that\r\nsolves the closest vector
problem for all l_p-norms, 1 < p < \\infty, in time p\r\nlog_2 (r)^{O (1)} n^{(5/2+o(1))n}
and for all polyhedral norms in time (s log_2\r\n(r))^{O (1)} n^{(2+o(1))n}, where
s is the number of constraints defining the\r\npolytope and r is an upper bound
on the coefficients used to describe the\r\nconvex body."
author:
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
- first_name: Stefanie
full_name: Naewe, Stefanie
last_name: Naewe
citation:
ama: Blömer J, Naewe S. Solving the Closest Vector Problem with respect to Lp Norms.
*arXiv:11043720*. 2011.
apa: Blömer, J., & Naewe, S. (2011). Solving the Closest Vector Problem with
respect to Lp Norms. *ArXiv:1104.3720*.
bibtex: '@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} }'
chicago: Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem
with Respect to Lp Norms.” *ArXiv:1104.3720*, 2011.
ieee: J. Blömer and S. Naewe, “Solving the Closest Vector Problem with respect to
Lp Norms,” *arXiv:1104.3720*. 2011.
mla: Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with
Respect to Lp Norms.” *ArXiv:1104.3720*, 2011.
short: J. Blömer, S. Naewe, ArXiv:1104.3720 (2011).
date_created: 2018-06-05T07:49:32Z
date_updated: 2019-01-03T13:13:55Z
department:
- _id: '64'
publication: arXiv:1104.3720
status: public
title: Solving the Closest Vector Problem with respect to Lp Norms
type: preprint
user_id: '25078'
year: '2011'
...