We 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 [R. Kannan, Math. Oper. Res., 12 (1987), pp. 415--440] and SIVP [D. Micciancio, Proceedings of the $19$th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 84--93] 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 [Proceedings of the $33$rd Annual ACM Symposium on Theory of Computing, 2001, pp. 266--275]. 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 a $2^{O(n \log\log n / \log n)}$ approximation factor.

The present work deals with the problem of information acquisition in a strategic networked environment. To study this problem, Kleinberg and Raghavan (FOCS 2005) introduced the model of query incentive networks, where the root of a binomial branching process wishes to retrieve an information -- known by each node independently with probability 1/n -- by investing as little as possible. The authors considered fixed-payment contracts in which every node strategically chooses an amount to offer its children paid upon information retrieval to convince them to seek the information in their subtrees. Kleinberg and Raghavan discovered that the investment needed at the root exhibits an unexpected threshold behavior that depends on the branching parameter b. For b>2, the investment is linear in the expected distance to the closest information (logarithmic in n, the rarity of the information), while, for 1<b<2, it becomes exponential in the same distance (i.e., polynomial in n). Arcaute et al. (EC 2007) later observed the same threshold behavior for arbitrary Galton-Watson branching processes.

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any n-dimensional lattice can be found in time 23.199n (and space 21.325n), or in space 21.095n (and still time 2O(n)). This improves the best previously known algorithm by Ajtai, Kumar and Sivakumar [Proceedings of STOC 2001] which was shown by Nguyen and Vidick [J. Math. Crypto. 2(2):181–207] to run in time 25.9n and space 22.95n. We also present a practical variant of our algorithm which provably uses an amount of space proportional to τn, the “kissing” constant in dimension n. No upper bound on the running time of our second algorithm is currently known, but experimentally the algorithm seems to perform fairly well in practice, with running time 20.52n, and space complexity 20.2n.

We give deterministic ~O(22n+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 nO(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 and asymptotically faster alternative to the 2O(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 2O(n) time and space complexity.