Shortest integer vectors

Shortest integer vectors

0.00 Avg rating0 Votes
Article ID: iaor1994676
Country: United States
Volume: 18
Issue: 3
Start Page Number: 516
End Page Number: 522
Publication Date: Aug 1993
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

Let A be a fixed integer matrix of size m by n and consider all b for which the body Kb={x:Ax•b} is full dimensional. The authors examine the set of shortest nonzero integral vectors with respect to the family of norms whose unit balls are given by (Kb-Kb). They show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. The authors also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree as the polynomial bound.

Reviews

Required fields are marked *. Your email address will not be published.