A DETERMINISTIC SINGLE EXPONENTIAL TIME ALGORITHM FOR MOST LATTICE PROBLEMS BASED ON VORONOI CELL COMPUTATIONS

作     者：Micciancio, Daniele Voulgaris, Panagiotis 

作者机构：Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Google Inc Mountain View CA 94043 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：2013年第42卷第3期

页      面：1364-1391页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CCF-0634909, CNS-0831536, CNS-1117936] Division Of Computer and Network Systems Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：lattice algorithms shortest vector problem closest vector problem Voronoi cell 

摘      要：We give deterministic (O) over tilde (2(2n))-time (O) over tilde (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 19th 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 33rd 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.