The shortest vector in a lattice is hard to approximate to within some constant.

被引：42

作者：

Micciancio, D ^{[1
]}

机构：

[1] MIT, Comp Sci Lab, Cambridge, MA 02139 USA

来源：

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1998年

关键词：

D O I：

10.1109/SFCS.1998.743432

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We show the shortest vector problem in the l(2) norm is NP-hard (for randomized reductions) to approximate within any constant factor less than root 2. We also give a deterministic reduction under a reasonable number theoretic conjecture. Analogous results hold in any l(p) norm (p greater than or equal to 1). In proving our NP-hardness result, we give an alternative construction satisfying Ajtai's probabilistic variant of Sauer's lemma; that greatly simplifies Ajtai's original proof.

引用

页码：92 / 98

页数：3