Brigitte Vallée

TCS Journal 2011 Journal Article

Philippe Flajolet, the Father of Analytic Combinatorics

• Bruno Salvy
• Bob Sedgewick
• Michèle Soria
• Wojciech Szpankowski
• Brigitte Vallée

TCS Journal 2003 Journal Article

Dynamical analysis of a class of Euclidean algorithms

• Brigitte Vallée

We develop a general framework for the analysis of algorithms of a broad Euclidean type. The average-case complexity of an algorithm is seen to be related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithm. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. As a consequence, we obtain precise average-case analyses of algorithms for evaluating the Jacobi symbol of computational number theory fame, thereby solving conjectures of Bach and Shallit. These methods also provide a unifying framework for the analysis of an entire class of gcd-like algorithms together with new results regarding the probable behaviour of their cost functions.

TCS Journal 1998 Journal Article

Continued fraction algorithms, functional operators, and structure constants

• Philippe Flajolet
• Brigitte Vallée

Continued fractions lie at the heart of a number of classical algorithms like Euclid's greatest common divisor algorithm or the lattice reduction algorithm of Gauss that constitutes a 2-dimensional generalization. This paper surveys the main properties of functional operators — transfer operators — due to Ruelle and Mayer (also following Lévy, Kuzmin, Wirsing, Hensley, and others) that describe precisely the dynamics of the continued fraction transformation. Spectral characteristics of transfer operators are shown to have many consequences, like the normal law for logarithms of continuants associated to the basic continued fraction algorithm and a purely analytic estimation of the average number of steps of the Euclidean algorithm. Transfer operators also lead to a complete analysis of the “Hakmem” algorithm for comparing two rational numbers via partial continued fraction expansions and of the “digital tree” algorithm for completely sorting n real numbers by means of their continued fraction representations. As a consequence, a small number of “structure constants” appear to govern the behaviour of a variety of continued fraction based algorithms.

SODA Conference 1998 Conference Paper

The Analysis of Hybrid Trie Structures

• Julien Clément 0001
• Philippe Flajolet
• Brigitte Vallée

TCS Journal 1994 Journal Article

An upper bound on the average number of iterations of the LLL algorithm

• Hervé Daudé
• Brigitte Vallée

An upper bound is established regarding the average number of iterations of the lattice reduction algorithm of Lenstra, Lenstra and Lovász (the LLL algorithm). The upper bound is of the form O(n 2 log n), where n is the dimension of the problem. It is essentially independent of the length of the input vectors, so that, in any fixed dimension, the LLL algorithm turns out to be of complexity O(1) on average.

FOCS Conference 1990 Conference Paper

The Lattice Reduction Algorithm of Gauss: An Average Case Analysis

• Brigitte Vallée
• Philippe Flajolet

The lattice reduction algorithm of Gauss is shown to have an average-case complexity that is asymptotic to a constant. The analysis makes use of elementary properties of continued fractions and of linear fractional transformations. >

STOC Conference 1989 Conference Paper

Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues

• Brigitte Vallée

Finding small quadratic residues modulo n, when n is a large composite number of unknown factorisation is almost certainly a computationally hard problem. This problem arises in a natural way when factoring n by the use of congruences of squares. We construct here a polynomial-time algorithm based on the use of lattices, which finds in a near uniform way quadratic residues mod n that are smaller than O(n 2/3 ). In this way, we derive a class of integer factorisation algorithms, the fastest of which provides the best rigorously established probabilistic complexity bound for integer factorisation algorithms.