Research activities



Publications:
Others:
  • Master thesis
  • PhD thesis

    Uniform random generation is a central issue in combinatorics. Under the Boltzmann model, combinatorial structures are generated with a randomly varying size, which allows for the design of particularly efficient samplers. The aim of this thesis is to make this sampling method effective for a large number of decomposable combinatorial classes via an automatization of all the treatments involved in the design of the samplers. The first part is dedicated to the study of sampling algorithms. We complete the initial dictionary of Boltzmann samplers in order to support unlabelled classes. Those generic algorithms are fully detailed, proved and illustrated by classical examples coming from combinatorics. Experimental data are given to emphasize the efficiency of those samplers. An application to the random generation of plane partitions concludes this study. In the framework of Boltzmann method, the samplers are parametrized with a numerical value that controls the expected size of the generated structures. The samplers uniformity relies on an oracle function that returns, for any combinatorial class, the value of its generating function at a given point. The second part of this thesis introduces a method to automatically and efficiently compute this oracle, using a numerical Newton iteration. The validity of this approach is based on the convergence of Newton iteration on combinatorial structures. This iteration is then lifted to the level of generating series and finally to numerical values. In addition, the iteration on series leads to a quasi-optimal algorithm to compute the first terms of the counting series.
    Slides


Software:

Talks:
    • Algorithms Project's Seminar, INRIA - november 14, 2005
    • SPIRAL's Team Seminar, LIP6 - november 18, 2005
    • Journées Arbres et Cartes, Bordeaux - december 2, 2005
    • Algorithms and combinatorics' seminar, LIAFA - february 14, 2006
    • ALEA06, Luminy - march 6, 2006
    • Summer school on Algorithmics and Computer Algebra, Bordeaux - may 15, 2006
  • GASCOM06, Dijon - september 14, 2006
  • ALEA07, Luminy - march 23, 2007
  • Algorithms Project's Seminar, INRIA - december 10, 2007 (long version)
    • ANR GAMMA, LIP6 - october 3, 2007
    • ForTesSE team's seminar, LRI (Univ. Orsay) - january 9, 2008
    • Seminar of the Gaspard-Monge Institute (Univ. Marne-la-Vallée) - march 25, 2008
    • International Workshop on Applied Probability, University of Compiegne (France) - july 10, 2008 (short version)
    • Seminar of the OCAD team, LIPN (Univ. Paris XIII) - march 3, 2009
    • TIFR, Mumbai, India - december 13, 2010 (new version)
    • LIP6 evaluation - january 17, 2008
    • ALEA08, Luminy - march 14, 2008
    • Algorithms Project's Seminar, INRIA - june 2, 2008 (long version, english)
    • Fifth Colloquium on Mathematics and Computer Science:
      Algorithms, Trees, Combinatorics and Probabilities, Blaubeuren, Germany - september 22-26, 2008
      (short version, english)
    • Groupe de travail de l'équipe combinatoire, LIX - january 14, 2009 (another long version)
    • Journées de Combinatoire de Bordeaux - february 4, 2009
    • FSTTCS 2010, Chennai, India - december 17, 2010
    • LIGM, Université Paris-Est Marne-la-Vallée - december 2011


Back to main page