---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Johannes
foaf_name: Blömer, Johannes
foaf_surname: Blömer
foaf_workInfoHomepage: http://www.librecat.org/personId=23
- foaf_Person:
foaf_givenName: Stefanie
foaf_name: Naewe, Stefanie
foaf_surname: Naewe
dct_date: 2011^xs_gYear
dct_title: Solving the Closest Vector Problem with respect to Lp Norms@
...