Short vector problems and simultaneous approximation
Daniel E. Martin · arXiv (Cornell University) · 2020
In 1982, Lagarias showed that solving the approximate Shortest Vector Problem also solves the problem of finding simultaneous Diophantine approximations. Here we provide the reverse reduction with polynomial complexity. It is gap-preserving provided a consistent norm is used to measure approximation quality in both problems. 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.