Reductions between short vector problems and simultaneous approximation
Daniel E. Martin · The Open Book Series · 2020
In 1982, Lagarias showed that solving the approximate shortest vector problem also solves the problem of finding good simultaneous Diophantine approximations (SIAM J. Comput., 14(1) :196-209, 1985)).Here we provide a deterministic, dimension-preserving reduction in the reverse direction.It has polynomial time and space complexity, and it is gap-preserving under the appropriate norms.We also give an alternative to the Lagarias algorithm by first reducing his version of simultaneous approximation to one with no explicit range in which a solution is sought.