Let's say I have a reduced basis $\mathcal{B}$ for an orthogonal lattice in $\mathbb{R}^n$, then the Shortest Vector Problem is trivial (the shortest vector in the basis). According to my intuition, the Closest Vector Problem on this lattice should also be easy. Is this the case, or am I missing something fundamental? I couldn't find a source, but I wasn't exactly sure what to search for.
Closest vector problem for orthogonal lattices
3
$\begingroup$
integer-lattices
-
0@TMM if you are willing to post your comment as an answer, I will accept it. – 2013-01-19
1 Answers
1
In 1985, László Babai gave two algorithms to solve the Closest Vector Problem, if the given vector is sufficiently close to the lattice and the basis of the lattice is sufficiently reduced. The source of these algorithms is this conference paper, and this follow-up journal paper.
The simplest of the two is Babai's rounding method, which basically rounds the coordinates (with respect to the input basis vectors) to the nearest integer, to obtain a lattice vector that is reasonably close. If your input basis is orthogonal, this will always find a closest vector, even if the given vector is far from the lattice.