A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems
| Autor: | Kevin Woods, John Goodrick, Tristram Bogart |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
General Mathematics Lattice problem Combinatorics Optimization and Control (math.OC) 52C07 TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Lattice (order) ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) Mathematics - Optimization and Control Mathematics Parametric statistics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 34:2363-2387 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/20m1327422 |
| Popis: | 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 (SVP) and closest vector problem (CVP) that are also eventually quasi-polynomial in t. Comment: 20 pages. Accepted for publication in SIAM Journal on Discrete Mathematics. Revised title and opening paragraphs, slightly modified statement of Theorem 1.4, added explanation of some steps in Section 3, and implemented various minor improvements suggested by anonymous referees |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|