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

DOI10.1017/S0963548397003258zbMath0921.11072OpenAlexW2160299629MaRDI QIDQ4372990

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 fractionsRuelle-Mayer operatorsGaussian algorithm for lattice reduction

Mathematics Subject Classification ID

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

Related Items

Special values of multiple polylogarithms, 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, Digits and continuants in Euclidean algorithms. Ergodic versus Tauberian theorems, PRECISE CALCULATION OF HAUSDORFF DIMENSION OF APOLLONIAN GASKET, Explicit formulas of sums involving harmonic numbers and Stirling numbers, Gaussian behavior of quadratic irrationals, Euler Sums and Contour Integral Representations