Reductions between short vector problems and simultaneous approximation

Abstract

In 1982, Lagarias showed that solving the approximate Shortest Vector Problem also solves the problem of finding good simultaneous Diophantine approximations. 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.

16 pages, 3 algorithms. Version 2 corrects a mistake in Proposition 2.1 that made it only correct under the sup norm, as well as an erroneous determinant computation that immediately followed Algorithm 3. Version 3 makes minor changes to match the published paper