Home

Programme

The talks will take place at the Amphi S3-057 which is located in Campus 2, in the "Sciences 3" building right in front of the terminus of the Tramway A.

A plan of the campus is available HERE.

Thursday, 3 June 2010

Friday, 4 June 2010

Abstracts

  • How Euclid really met Gauss, through Dolgopyat (and Brigitte), Viviane Baladi (ENS Paris).

    On September 24, 2001, I had dinner with Brigitte Vallée, Philippe Flajolet, and Brigitte Chauvin in a restaurant in Versailles. Either the tablecloth was made of paper, or she used a napkin. In any case, at the end of the meal (civilised mathematicians have priorities!), Brigitte Vallée asked me whether a specific spectral property of parametrised dynamical transfer operators was plausible, because she knew it would have important consequences on the analysis in distribution of Euclidean algorithms. Luckily, I knew that Dmitry Dolgopyat had recently proved exactly the kind of estimates that Brigitte was dreaming about. In this talk, I will explain the results that Brigitte and I obtained as a consequence of this Versailles dinner, and how they fit in the fruitful research programme that she had started to develop in the nineties.

  • Muldimensional Euclid's algorithms in discrete geometry, Valérie Berthé (CNRS - LIAFA, Université de Paris 7)

    Euclid's algorithm is known to describe in full generality all geometric and combinatorial properties of discrete lines. Discrete lines are defined here as sets of points with integer coordinates that are selected within a bounded distance of a Euclidean line. One similarly defines discrete planes. It is well-known that there is no canonical multidimensional version of Euclid's algorithm. Furthermore, no multidimensional Euclid's algorithm has yet won recognition in the study of discrete planes. The aim of this lecture is to discuss properties that are required in discrete geometry for such an algorithm and more generally for a multidimensional continued fraction algorithm. These properties will be considered both from the Dynamical Analysis prospective and from an arithmetic, combinatorial and geometric viewpoint.

  • Dynamical sources in information theory, Jérémie Bourdon (IRISA & Université de Nantes)

    In the last two decades, Brigitte Vallée and its group developed the so-called dynamical analysis theory. One of its major application is that is allows to define a very general probabilistic model of word generation named dynamical sources. Such sources are very flexible in the sense that they handle unbounded correlations between symbols of the generated sequences. In this talk, we remind their main properties together with some of their important applications to the study of data structures and pattern matching problems. This thus consists in a « panorama » of Brigitte’s group contributions to information theory.

  • Real and rational numbers with restricted digits and Hausdorff dimension, Eda Cesaratto (Universidad Nacional de General Sarmiento and Conicet, Argentina)

    A dynamical source provides a way of coding real numbers with an infinite string of digits. In this talk, we deal with the set of real and rational numbers which obey some constraints on their digits. In the real case, (almost) all sets have zero Lebesgue measure, even though the nature of the constraints and the dynamical sources are very different. Sets of zero measure appear in many areas of science, and Hausdorff dimension has shown to be an appropriate tool for studying their nature. Classically, the studied constraints involve each digit in an independent way. Here, more global conditions are studied. The main example of interest deals with reals whose all the digit prefix averages in their continued fraction expansion are bounded by M. More generally, a weight function is defined on the digits, and the weighted average of each prefix has to be bounded by M. Hausdorff dimension is characterized in terms of the dominant eigenvalue of the weighted operator transfer operator relative to the dynamical system, in quite a general setting. We then come back to our main example; with the previous characterization at hand and use of the Mellin Transform, we exhibit the asymptotic of Hausdorff dimension with respect to M.

    In the discrete case, the focus is on continued fraction sources and rational numbers. In this case, Hausdorff dimension appears in estimates of the cardinality of the set of rational numbers of denominator less than N whose digits are less than a given bound M(N). Estimates of this cardinality have been obtained by Cusick, Hensley and Vallée. In this talk, we describe how the dynamical analysis method, introduced by Vallée and refined by Baladi and Vallée in 2005, allows to obtain improvements to Hensley's and Cusick's estimates.

  • Local repetitions in strings, Maxime Crochemore (King's College London and Université Paris-Est)

    The analysis of repetition in strings constitutes a fundamental area of combinatorics on words due to important applications to text algorithms, data compression, music analysis, and biological sequences analysis.

    The talk surveys algorithmic methods used to locate repetitive segments in strings. It discusses the notion of runs that encompasses various types of periodicities considered by different authors. The analysis of related algorithms raises interesting combinatorial questions and conjectures.

     

  • Random formula and phase transitions, Hervé Daudé (Université de Aix-Marseille)

    We will present some combinatorial tools well suited to the probabilistic study of Constraint Satisfaction Problems.

  • LAVDATIO, Philippe Flajolet (INRIA Rocquencourt)

    See title.

  • Recent and astounding discovery of hard (to decrypt) bits (of paper), X-Ray dated end of 70's, and attributed by worldclass scientific experts to Pr. B. Vallee, Marc Girault (GREYC, Université de Caen)

    See title.

  • Computing the invariant density for the Hurwitz complex continued fraction algorithm, Doug Hensley (Université de Texas, USA)

    The Hurwitz complex continued fraction algorithm gives a continued fraction expansion of a complex number z=x+iy inside the box B given by -1/2 < x ≤ 1/2, -1/2<y ≤ 1/2 by sending z to 1/z, then subtracting a + ib = ⌊x + 1/2⌋ + i⌊y + 1/2⌋ from 1/z. The successive a + ib's give the continued fraction digits of z. This algorithm is known to have an invariant density, something akin to the Gauss density 1/((1 + x) log 2) for the classical continued fraction, but for the complex counterpart, no formula is known and no reasonable algorithm for computing an approximation to the density seems to be known.

    We offer an algorithm based on the representation of the density as an ensemble of series expansions, one for each of the twelve regions into which B is naturally divided by the action of the Hurwitz continued fraction. The computations are complicated by the need to compute double sums approximately, which requires a two-layered Euler-Maclaurin estimation. One encounters hypergeometric functions as well as the Hurwitz zeta function along the way. The method should in principle give approximations good to d digits in time and space resources that grow polynomially with d.

  • Reduction and Minkowskian sublattices, Jacques Martinet (Université de Bordeaux)

    Let Λ be a lattice in an n-dimensional Euclidean space E. Set N(x) = x · x (the “norm” of x). One considers ratios

    (N(e1)…N(en))/ det(Λ)    (*)
    on either a basis (e1, ..., en) for Λ (Hermite) or on a set {e1, ..., en} of independent vectors of Λ (Minkowski, the successive minima of Λ; we call “Minkowskian” a sublattice generated by these minima).

     

    In this talk we consider several questions related to Minkowskian sublattices, which actually reduce to the case of well-rounded lattices, those lattices which possess systems of n independent minimal vectors : bounds for the index and Z/dZ-codes associated with Mikowskian sublattices, Louis Michel's problem of bases of minimal vectors, improvement of inequalities of van der Waerden related to (*).

    The results above heavily rely on joint work with Achill Schürmann.

  • Average Time Fast SVP and CVP Algorithms for Low Density Lattices and the Factorization of Integers, Claus Peter Schnorr (Université de Francfort)

    We propose and analyze novel algorithms for finding shortest and closest lattice vectors. The algorithm New Enum performs the stages of exhaustive enumeration of short / close lattice vectors in order of decreasing success rate. We analyze New Enum under GSA which in practice holds on the average for well reduced bases. New Enum solves SVP in nn/8+o(n) time for bases of dimension n that satisfy GSA. Under the volume heuristics a shortest lattice vector is found in polynomial time if the density of the lattice is moderately small. This might affect the RSA scheme. Integers N can be factored by solving (ln N)O(1) CVP's for the prime number lattice. Under combined standard and new heuristics these CVP's are solvable in polynomial time.

  • TBA, Jacques Stern (ENS Paris) sous réserve