Polynomial Time Algorithms for Finding Integer Relations among Real Numbers

DOI10.1137/0218059zbMath0692.10033OpenAlexW2027157239WikidataQ56959232 ScholiaQ56959232MaRDI QIDQ3033848

Jeffrey C. Lagarias, Bettina Just, Johan T. Håstad, Claus Peter Schnorr

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218059

zbMATH Keywords

continued fractionapproximation algorithmscomputational number theoryinteger relationmultidimensional Euclidean algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Continued fractions and generalizations (11J70) Continued fraction calculations (number-theoretic aspects) (11Y65) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items (28)

Complexity results for some eigenvector problems ⋮ Towards faster polynomial-time lattice reduction ⋮ Lattice basis reduction: Improved practical algorithms and solving subset sum problems ⋮ Recovering Exact Results from Inexact Numerical Data in Algebraic Geometry ⋮ An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\) ⋮ Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation ⋮ Real data-integer solution problems within the Blum-Shub-Smale computational model ⋮ Simultaneously good bases of a lattice and its reciprocal lattice ⋮ Cloud-Assisted LLL: A Secure and Efficient Outsourcing Algorithm for Approximate Shortest Vector Problem ⋮ Experimental Evaluation of Euler Sums ⋮ Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms ⋮ Trilateration using unlabeled path or loop lengths ⋮ The PSLQ algorithm for empirical data ⋮ Thrackles: An Improved Upper Bound ⋮ Parallel integer relation detection: Techniques and applications ⋮ An optimal, stable continued fraction algorithm for arbitrary dimension ⋮ Distances from differences of roots of polynomials to the nearest integers ⋮ Improved low-density subset sum algorithms ⋮ Random Sampling Revisited: Lattice Enumeration with Discrete Pruning ⋮ A natural lattice basis problem with applications ⋮ Fast LLL-type lattice reduction ⋮ Selected Applications of LLL in Number Theory ⋮ A Numerical Transcendental Method in Algebraic Geometry: Computation of Picard Groups and Related Invariants ⋮ On the hardness of approximating shortest integer relations among rational numbers ⋮ Factoring polynomials over global fields ⋮ Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey ⋮ Analysis of PSLQ, an integer relation finding algorithm ⋮ Simultaneous reduction of a lattice basis and its reciprocal basis

This page was built for publication: Polynomial Time Algorithms for Finding Integer Relations among Real Numbers