Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it is named "closest vector problem".

Is it correct that "hardness" comes from the "lattice reduction" step ? I mean if in our lattice we can easily get the shortest and any other vector or basis we want then problem becomes not NP-hard ?

Some related posts: How to find nearest lattice point to given point in R^n ? Is it NP ?

Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z) , (SL(4,Z)) ?

How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ?

share|improve this question

1 Answer 1

up vote 9 down vote accepted

It actually remains hard, although not as hard. See the paper Hardness of approximating the closest vector problem with pre-processing by Alekhnovich, Khot, Kindler, and Vishnoi (FOCS 2005, http://www.math.ias.edu/~misha/papers/cvpp.pdf). They show that even if you are allowed to do arbitrary pre-processing after having been given the lattice basis but before seeing the target vector, you still can't get a better approximation factor than $(\log n)^{1/2-\varepsilon}$, assuming your calculations after seeing the target vector must run in polynomial time, and assuming that there are no quasi-polynomial-time algorithms for NP.

However, you do get real benefit from being able to do lattice basis reduction in advance (not just LLL reduction, but something more computationally intensive). For example, Lagarias, Lenstra, and Schnorr showed that using Korkine-Zolotarev reduction, you could get an $n^{1.5}$ approximation factor (Combinatorica 10 (1990), 333–348). In FOCS 2004, Aharonov and Regev got a $\sqrt{n/\log n}$ approximation factor with pre-processing. However, in all these algorithms the pre-processing requires more than polynomial time.

share|improve this answer
    
Thank You very much ! Where does the complexity comes from? If I am not making mistake in R^2 after reduction the closest vector can be found quite simply... Can the same be done in R^4 R^3? –  Alexander Chervov Apr 18 '11 at 17:53
    
In any fixed dimension the closest vector problem can be solved in polynomial time, for example by using Lenstra's fixed-dimension integer programming algorithm (although there are better methods; see, for example, Ravi Kannan's 1983 STOC paper Improved algorithms for integer programming and related lattice problems). So the difficulty comes from large dimensions. –  Henry Cohn Apr 18 '11 at 23:57
    
Thank You very much ! What are the best current methods to do this in small dimensions 2,4, 8 ? –  Alexander Chervov Apr 22 '11 at 20:03

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.