ECCC-Report TR10-014https://eccc.weizmann.ac.il/report/2010/014Comments and Revisions published for TR10-014en-usSat, 03 Mar 2012 02:35:40 +0200
Revision 1
| A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations |
Daniele Micciancio,
Panagiotis Voulgaris
https://eccc.weizmann.ac.il/report/2010/014#revision1We give deterministic $\tilde{O}(2^{2n})$-time $\tilde{O}(2^n)$-space algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, Math. Operation Research 12(3):415-440, 1987) and SIVP (Micciancio, SODA 2008), and gives a deterministic and asymptotically faster alternative to the $2^{O(n)}$-time (and space) randomized algorithm for SVP of (Ajtai, Kumar and Sivakumar, STOC 2001). The core of our algorithm is a new method to solve the Closest Vector Problem with Preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. A direct consequence of our results is a derandomization of the best current polynomial time approximation algorithms for SVP and CVP achieving $2^{O(n \log\log n / \log n)}$ approximation factor.
Sat, 03 Mar 2012 02:35:40 +0200https://eccc.weizmann.ac.il/report/2010/014#revision1
Paper TR10-014
| A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations |
Daniele Micciancio,
Panagiotis Voulgaris
https://eccc.weizmann.ac.il/report/2010/014We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP).
This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, Math. Operation Research 12(3):415-440, 1987) and SIVP (Micciancio, Proc. of SODA, 2008), and gives a deterministic alternative to the $2^{O(n)}$-time (and space) randomized algorithm for SVP of (Ajtai, Kumar and Sivakumar, STOC 2001). The core of our algorithm is a new method to solve the closest vector problem with preprocessing (CVPP) that uses the Voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. In the process, we also give algorithms for several other lattice problems, including computing the kissing number of a lattice, and computing the set of all Voronoi relevant vectors. All our algorithms are deterministic, and have $2^{O(n)}$ time and space complexity.Tue, 02 Feb 2010 08:41:37 +0200https://eccc.weizmann.ac.il/report/2010/014