Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
@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. –  Tim Seguine Nov 26 '12 at 12:15
    
I thought the second paragraph there was what you asked for (Though, there is a typo in that line which needs to be fixed)? –  TenaliRaman Nov 26 '12 at 16:27
    
@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. –  Tim Seguine Nov 28 '12 at 15:26
    
ah yes you are right. Apologies, I was truly confused by the wording given there. Sorry about that. –  TenaliRaman Nov 28 '12 at 15:34

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.