检索结果-内蒙古大学图书馆

The inapproximability of lattice and coding problems with preprocessing

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2004年第1期69卷 45-67页

作者： Feige, U Micciancio, D Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Weizmann Inst Sci IL-76100 Rehovot Israel

We prove that the closest vector problem with preprocessing (CVPP) is NP-hardto approximate within any factor less than (5/3)~(1/2). More specifically, we show that thereexists a reduction from an NP-hard problem to the approximate closest vector problem such that thelattice depends only on the size of the original problem, and the specific instance is encodedsolely in the target vector. It follows that there are lattices for which the closest vector problemcannot be approximated within factors γ<(5/3)~(1/2) in polynomial time, no matter how the latticeis represented, unless NP is equal to P (or NP is contained in P/poly, in case of nonuniformsequences of lattices). The result easily extends to any l_p norm, for p≥ 1, showing that CVPP inthe l_p norm is hard to approximate within any factor γ < p (5/3)~(1/p). As an intermediate step,we establish analogous results for the nearest codeword problem with preprocessing (NCPP), provingthat for any finite field GF(q), NCPP over GF(q) is NP-hard to approximate within any factor lessthan 5/3.

关键词： point lattices coding theory closest vector problem nearest codeword problem preprocessing computational complexity NP-hardness approximation problems

来源：评论

学校读者我要写书评

暂无评论

The inapproximability of lattice and coding problems with preprocessing

The inapproximability of lattice and coding problems with pr...

引用

17th IEEE Annual Conference on computational complexity

作者： Feige, U Micciancio, D Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA Weizmann Inst Sci IL-76100 Rehovot Israel

ISBN: (纸本)0769514685

We prove that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate within any factor less than √5/3. More specifically, we show that there exists a reduction from an NP-hard problem to the approximate closest vector problem such that the lattice depends only on the size of the original problem, and the specific instance is encoded solely in the target vector. It follows that there are lattices for which the closest vector problem cannot be approximated within factors γ<√5/3 in polynomial time, no matter how the lattice is represented, unless NP is equal to P (or NP is contained in P/poly, in case of nonuniform sequences of lattices). The result easily extends to any ℓ_p norm, for p≥1, showing that CVPP in the ℓ_p norm is hard to approximate within any factor γpreprocessing (NCPP), proving that for any finite field GF(q),NCPP over GF(q) is NP-hard to approximate within any factor less than 5/3. © 2004 Published by Elsevier Inc.

关键词： point lattices coding theory closest vector problem nearest codeword problem preprocessing computational complexity NP-hardness approximation problems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：