{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:38:37Z","timestamp":1787323117903,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100006070","name":"Universidad de los Andes","doi-asserted-by":"publisher","award":["INV-2017-51-1453"],"award-info":[{"award-number":["INV-2017-51-1453"]}],"id":[{"id":"10.13039\/501100006070","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>Given a parametric lattice with a basis given by polynomials in $\\Bbb{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$.<\/jats:p>","DOI":"10.1137\/20m1327422","type":"journal-article","created":{"date-parts":[[2020,11,12]],"date-time":"2020-11-12T13:00:33Z","timestamp":1605186033000},"page":"2363-2387","source":"Crossref","is-referenced-by-count":3,"title":["A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems"],"prefix":"10.1137","volume":"34","author":[{"given":"Tristram","family":"Bogart","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Goodrick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Woods","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,11,12]]},"reference":[{"key":"atypb1","first-page":"10","author":"Ajtai M.","year":"1998","journal-title":"ACM"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork,\n                      A public-key cryptosystem with worst-case\/average-case equivalence\n                      , in Proceedings of the 29th ACM Symposium on Theory of Computating, 1997, pp. 284-293,https:\/\/doi.org\/10.1145\/258533.258604.","DOI":"10.1145\/258533.258604"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Barvinok,\n                      Integer Points in Polyhedra\n                      , Zur. Lect. Adv. Math. 452, European Mathematical Society, 2008,https:\/\/doi.org\/10.4171\/052.","DOI":"10.4171\/052"},{"key":"atypb5","first-page":"10","volume":"4","author":"Bogart T.","year":"2017","journal-title":"Discrete Anal."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05775-3"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05494-2"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"S. D. Galbraith,\n                      Mathematics of Public Key Cryptography\n                      , Cambridge University Press, Cambridge, UK, 2012,https:\/\/doi.org\/10.1017\/cbo9781139012843.028.","DOI":"10.1017\/CBO9781139012843"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"C. F. Gauss,\n                      Disquisitiones Arithmeticae\n                      (1801), Yale University Press, New Haven, 1966,https:\/\/doi.org\/10.1007\/978-1-4939-7560-0.","DOI":"10.5479\/sil.324926.39088000932822"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00019-7"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/16M1102458"},{"key":"atypb14","unstructured":"P. van Emde Boas,\n                      Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice\n                      , Technical Report 81-04, Mathematische Institut, University of Amsterdam, 1981."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.37236\/3750"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1327422","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:42:47Z","timestamp":1787319767000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1327422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/20M1327422"],"URL":"https:\/\/doi.org\/10.1137\/20m1327422","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}