✦ LIBER ✦

Note on shortest and nearest lattice vectors

✍ Scribed by Martin Henk

Book ID: 104137357
Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 450 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00019-7

No coin nor oath required. For personal study only.

✦ Synopsis

We show that with respect to a certain class of norms the so-called shortest lattice vector problem is polynomial-time Turing (Cook) reducible to the nearest lattice vector problem. This gives a little more insight in the relationship of these two fundamental problems in the computational geometry of numbers. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

On Polynomial-Factor Approximations to t

On Polynomial-Factor Approximations to the Shortest Lattice Vector Length

✍ Kumar, Ravi; Sivakumar, D. 📂 Article 📅 2003 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 102 KB

Dual vectors and lower bounds for the ne

Dual vectors and lower bounds for the nearest lattice point problem

✍ J. Hastad 📂 Article 📅 1988 🏛 Springer-Verlag 🌐 English ⚖ 318 KB

A relation of primal-dual lattices and t

A relation of primal-dual lattices and the complexity of shortest lattice vector problem

✍ Jin-Yi Cai 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 891 KB

Note on the -vectors of cutsets in the s

Note on the -vectors of cutsets in the subspace lattice

✍ Feng, Hong; Zhou, Roberta R. 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 364 KB

Notes on the Stone property in vector la

Notes on the Stone property in vector lattices

✍ John S. Pym 📂 Article 📅 1968 🏛 Springer 🌐 English ⚖ 450 KB

On Lovász’ lattice reduction and the nea

On Lovász’ lattice reduction and the nearest lattice point problem

✍ L. Babai 📂 Article 📅 1986 🏛 Springer-Verlag 🌐 English ⚖ 561 KB