A polynomial time algorithm for GapCVPP in l_1 norm  

作　　者：TIAN ChengLiang HAN LiDong XU GuangWu 

机构地区：[1]Key Laboratory of Cryptologic Technology and Information Security,Ministry of Education,Shandong University [2]School of Mathematics,Shandong University [3]Institute for Advanced Study,Tsinghua University [4]Department of Electrical Engineering and Computer Science,University of Wisconsin-Milwaukee

出　　处：《Science China(Information Sciences)》2014年第3期107-113,共7页中国科学（信息科学）（英文版）

基　　金：supported by National Basic Research Program of China(973 Program)(Grant No.2013CB8342-05);National Natural Science Foundation of China(Grant Nos.61133013,61272035)

摘　　要：This paper concerns the hardness of approximating the closest vector in a lattice with preprocessing in 11 norm, and gives a polynomial time algorithm for GapCVPP~ in 11 norm with gap ＂y ---- 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.This paper concerns the hardness of approximating the closest vector in a lattice with preprocessing in 11 norm, and gives a polynomial time algorithm for GapCVPP~ in 11 norm with gap ＂y ---- 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.

关 键 词：LATTICES ALGORITHM Laplace measures closest vector problem with preprocessing computational complexity 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]