Solving low-density multiple subset sum problems with SVP oracle

doi:10.1007/s11424-015-3324-9

CSpace > 系统科学研究所

	Solving low-density multiple subset sum problems with SVP oracle
	Pan Yanbin; Zhang Feng
	2016-02-01
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
卷号	29 期号:1 页码:228-242
摘要	It is well known that almost all subset sum problems with density less than 0.9408 center dot center dot center dot can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice. In this paper, the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution. Specially, for the single subset sum problem (k = 1), a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before. Moreover, some extended versions of the multiple subset sum problem are also considered.
关键词	Lattice low-density multiple modular subset sum problem multiple subset sum problem
DOI	10.1007/s11424-015-3324-9
语种	英语
资助项目	National Natural Science Foundation of China[11201458] ; National Natural Science Foundation of China[11471314] ; 973 Project[2011CB302401] ; National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000370162300014
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22035
专题	系统科学研究所
通讯作者	Pan Yanbin; Zhang Feng
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, NCMIS, Key Lab Math Mechanizat, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Pan Yanbin,Zhang Feng. Solving low-density multiple subset sum problems with SVP oracle[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2016,29(1):228-242.
APA	Pan Yanbin,&Zhang Feng.(2016).Solving low-density multiple subset sum problems with SVP oracle.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,29(1),228-242.
MLA	Pan Yanbin,et al."Solving low-density multiple subset sum problems with SVP oracle".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 29.1(2016):228-242.