An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction

DOI10.1017/S0963548397003258MaRDI QIDQ4372990zbMATH OpenOpenAlexFDO

Authors Hervé Daudé, Brigitte Vallée, Philippe Flajolet

Publication date 18 December 1997

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548397003258

zbMATH Keywords

continued fractionsGaussian algorithm for lattice reductionRuelle-Mayer operators

Mathematics Subject Classification ID

Minima of forms (11H50) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 799773
• Publication:4860760
• scientific article; zbMATH DE number 5763317
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss

Cited in

(17)

• Continued fraction algorithms, functional operators, and structure constants
• The optimal LLL algorithm is still polynomial in fixed dimension.
• Dynamical analysis of a class of Euclidean algorithms.
• Volumes and distributions for random unimodular complex and quaternion lattices
• Spectral analysis for the Gauss problem on continued fractions
• On the stack-size of general tries
• The Generalized Gauss Reduction Algorithm
• Euler Sums and Contour Integral Representations
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
• Special values of multiple polylogarithms
• scientific article; zbMATH DE number 799774 (Why is no real title available?)
• scientific article; zbMATH DE number 834675 (Why is no real title available?)
• Precise calculation of Hausdorff dimension of Apollonian gasket
• Explicit formulas of sums involving harmonic numbers and Stirling numbers
• Gaussian behavior of quadratic irrationals
• Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems
• Rational approximations, multidimensional continued fractions, and lattice reduction

This page was built for publication: An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction

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