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 quasioptimal 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 GaspardMonge Institute (Univ. MarnelaVallé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
 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 2226, 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é ParisEst MarnelaVallée  december 2011

