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 (12)

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

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