A polynomial time algorithm for GapCVPP in l_1 norm | |
TIAN ChengLiang ; HAN LiDong ; XU GuangWu ; TIAN ChengLiang ; HAN LiDong ; XU GuangWu | |
2016-03-30 ; 2016-03-30 | |
关键词 | lattices algorithm Laplace measures closest vector problem with preprocessing computational complexity TP301.6 |
其他题名 | A polynomial time algorithm for GapCVPP in l_1 norm |
中文摘要 | 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 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 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 main technical ingredient used in this paper is the discrete Laplace distribution on lattices which may be of independent interest. |
语种 | 英语 ; 英语 |
内容类型 | 期刊论文 |
源URL | [http://ir.lib.tsinghua.edu.cn/ir/item.do?handle=123456789/143090] |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | TIAN ChengLiang,HAN LiDong,XU GuangWu,et al. A polynomial time algorithm for GapCVPP in l_1 norm[J],2016, 2016. |
APA | TIAN ChengLiang,HAN LiDong,XU GuangWu,TIAN ChengLiang,HAN LiDong,&XU GuangWu.(2016).A polynomial time algorithm for GapCVPP in l_1 norm.. |
MLA | TIAN ChengLiang,et al."A polynomial time algorithm for GapCVPP in l_1 norm".(2016). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论