Timeline for Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2011 at 20:03 | comment | added | Alexander Chervov | Thank You very much ! What are the best current methods to do this in small dimensions 2,4, 8 ? | |
| Apr 18, 2011 at 23:57 | comment | added | Henry Cohn | 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. | |
| Apr 18, 2011 at 17:53 | comment | added | Alexander Chervov | 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? | |
| Apr 18, 2011 at 17:36 | vote | accept | Alexander Chervov | ||
| Apr 18, 2011 at 13:33 | history | answered | Henry Cohn | CC BY-SA 3.0 |