6
$\begingroup$

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 ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Alexander Chervov
    Commented Apr 18, 2011 at 17:53
  • $\begingroup$ 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. $\endgroup$
    – Henry Cohn
    Commented Apr 18, 2011 at 23:57
  • $\begingroup$ Thank You very much ! What are the best current methods to do this in small dimensions 2,4, 8 ? $\endgroup$
    – Alexander Chervov
    Commented Apr 22, 2011 at 20:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .