标题:A polynomial time algorithm for GapCVPP in l_1 norm
作者:TIAN ChengLiang;HAN LiDong;XU GuangWu;
作者机构:[TIAN ChengLiang;HAN LiDong;XU GuangWu]Key Laboratory of Cryptologic Technology and Information Security,Ministry of Education,Shandong University;[TI 更多
通讯作者:Tian, CL
通讯作者地址:[Tian, CL]Shandong Univ, Key Lab Cryptol Technol & Informat Secur, Minist Educ, Jinan 250100, Peoples R China.
来源:Science China(Information Sciences)
出版年:2014
卷:57
期:3
页码:112-118
DOI:10.1007/s11432-013-4795-8
关键词:lattices;algorithm;Laplace measures;closest vector problem with preprocessing;computational complexity
摘要: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/log n).The gap is smaller than that obtained by simply generalizing the approach given by Aharonov and Regev.The ma...
收录类别:SCOPUS;SCIE
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=JFXG201403010&DbName=CJFQ2014
TOP