标题：A polynomial time algorithm for GapCVPP in l1norm
作者：Tian, ChengLiang ;Han, LiDong ;Xu, GuangWu
作者机构：[Tian, ChengLiang ] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, 250100, Chin 更多
通讯作者：Tian, C L
来源：Science China Information Sciences
摘要：This paper concerns the hardness of approximating the closest vector in a lattice with preprocessing in l1norm, and gives a polynomial time algorithm for GapCVPPγin l1norm with gap γ = O(n/logn). The gap is smaller than that obtained by simply generalizing the approach given by Aharonov and Regev. The main technical ingredient used in this paper is the discrete Laplace distribution on lattices which may be of independent interest. © 2013 Science China Press and Springer-Verlag Berlin Heidelberg.