论文标题
短矢量问题与同时近似之间的减少
Reductions between short vector problems and simultaneous approximation
论文作者
论文摘要
1982年，拉加里亚斯（Lagarias）表明，解决近似最短的载体问题也解决了找到良好同时双养耐药近似值的问题。在这里，我们在反向方向上提供了确定性的，更具维度的降低。它具有多项式时间和空间的复杂性，并且在适当的规范下具有差距性。我们还通过首先将他的同时近似版本减少到没有明确的范围的范围，从而替代了Lagarias算法。
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.
