科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper concerns the hardness of approximating the closest vector in a lattice with preprocessing in l(1) norm, and gives a polynomial time algorithm for GapCVPP(gamma) in l(1) norm with gap gamma = O(n/log n). 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.
