Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:04:28Z http://mathoverflow.net/feeds/question/62116 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62116/closest-vector-problem-nearest-lattice-point-is-trivial-for-reduced-lattice Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ? Alexander Chervov 2011-04-18T12:37:48Z 2011-04-18T13:33:31Z <p>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". </p> <p>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 ? </p> <p>Some related posts: <a href="http://mathoverflow.net/questions/61897/how-to-find-nearest-lattice-point-to-given-point-in-rn-is-it-np" rel="nofollow">http://mathoverflow.net/questions/61897/how-to-find-nearest-lattice-point-to-given-point-in-rn-is-it-np</a></p> <p><a href="http://mathoverflow.net/questions/61933/lattice-reduction-in-r3-r4-or-what-is-fundamental-domain-for-sl3-z-sl4" rel="nofollow">http://mathoverflow.net/questions/61933/lattice-reduction-in-r3-r4-or-what-is-fundamental-domain-for-sl3-z-sl4</a></p> <p><a href="http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or" rel="nofollow">http://mathoverflow.net/questions/61945/how-often-does-lll-reduction-produce-optimal-result-is-there-condition-or</a></p> http://mathoverflow.net/questions/62116/closest-vector-problem-nearest-lattice-point-is-trivial-for-reduced-lattice/62121#62121 Answer by Henry Cohn for Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ? Henry Cohn 2011-04-18T13:33:31Z 2011-04-18T13:33:31Z <p>It actually remains hard, although not as hard. See the paper <em>Hardness of approximating the closest vector problem with pre-processing</em> by Alekhnovich, Khot, Kindler, and Vishnoi (FOCS 2005, <a href="http://www.math.ias.edu/~misha/papers/cvpp.pdf" rel="nofollow">http://www.math.ias.edu/~misha/papers/cvpp.pdf</a>). 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.</p> <p>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.</p>