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
-
0http://en.wikipedia.org/wiki/Lattice_problem#Relationship_with_SVP – 2012-11-26
-
0@TenaliRaman That is the opposite direction. I know that in general I can't expect it to be true, but this is a specific lattice. – 2012-11-26
-
0I thought the second paragraph there was what you asked for (Though, there is a typo in that line which needs to be fixed)? – 2012-11-26
-
0@TenaliRaman The wording is confusing, but it seems to take a lattice basis, and uses CVP to compute the shortest vector in the lattice. This is not what I am after, since I already know how to find the shortest vector. – 2012-11-28
-
0ah yes you are right. Apologies, I was truly confused by the wording given there. Sorry about that. – 2012-11-28
-
0@TenaliRaman not a problem. After your second post, I had to reread that paragraph about a dozen times before I was sure. – 2012-11-29
-
0By orthogonal, do you mean that your basis vectors are orthogonal? Then CVP is indeed trivial; just use e.g. Babai's rounding method. – 2012-12-30
-
0@TMM That was my intuition, but I was afraid I was missing something. – 2013-01-02
-
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.