Paper Info
Title
A Parametric Version Of Lll And Some Consequences: Parametric Shortest And Closest Vector Problems
Abstract
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem and closest vector problem that are also eventually quasi-polynomial in t.
Year
DOI
Venue
2020
10.1137/20M1327422
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
lattices, LLL algorithm, shortest vector problem, parametric lattices
Journal
34
Issue
ISSN
Citations 
4
0895-4801
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Tristram Bogart1133.54
John Goodrick2267.57
Kevin M. Woods3256.04