Reductions between short vector problems and simultaneous approximation

DOI10.2140/OBS.2020.4.335MaRDI QIDQ5853807zbMATH OpenOpenAlexFDO

Authors Daniel E. Martin

Publication date 11 March 2021

Published in Open Book Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.12173

zbMATH Keywords

lattice reductionshortest vector problemsimultaneous approximationsimultaneous Diophantine approximation

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Simultaneous homogeneous approximation, linear forms (11J13) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)

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.

Recommendations

• scientific article; zbMATH DE number 3908520
• Approximating the closest vector problem using an approximate shortest vector oracle
• scientific article; zbMATH DE number 3972987
• Inapproximability of the shortest vector problem: toward a deterministic reduction
• Simultaneous reduction of a lattice basis and its reciprocal basis

Cited in

(2)

• Finding simultaneous Diophantine approximations with prescribed quality
• Approximating the closest vector problem using an approximate shortest vector oracle

This page was built for publication: Reductions between short vector problems and simultaneous approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853807)