Session S24 - Symbolic Computation: Theory, Algorithms and Applications

Tuesday, July 13, 17:00 ~ 17:25 UTC-3

A parametric version of the LLL algorithm and consequences

Tristram Bogart

Universidad de los Andes, Colombia   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Given a parametric lattice with a basis given by polynomials with integer coefficients, 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.

Joint work with John Goodrick (Universidad de los Andes, Colombia) and Kevin Woods (Oberlin College, USA).

View abstract PDF