New Hardness Results for Diophantine Approximation

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error bound \epsilon and a denominator bound N. One has to decide whether there exists an integer, called the denominator Q with 1