Research activities

Publications:

Boltzmann Sampling of Unlabelled Structures,
P. Flajolet, E. Fusy and C. Pivoteau. In
Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, in , D. Applegate, G.S. Brodal, D. Panario, and R. Sedgewick, eds., vol. 126 of SIAM Proceedings in Applied Mathematics, SIAM, 2007, pp. 201211. Workshops held in New Orleans, LA, January 6, 2007.
BibTeX
Boltzmann models from statistical physics, combined
with methods from analytic combinatorics, give rise to efficient
algorithms for the random generation of unlabelled objects. The
resulting algorithms generate in an unbiased manner discrete
configurations that may have nontrivial symmetries, and they do so
by means of realarithmetic computations. Here you'll find a
collection of construction rules for such samplers, which applies to
a wide variety of combinatorial classes, including integer
partitions, necklaces, unlabelled functional graphs, dictionaries,
seriesparallel circuits, term trees and acyclic molecules obeying a
variety of constraints.

Random sampling of plane partitions O. Bodini,
E. Fusy, C. Pivoteau.
In Combinatorics, Probability & Computing 2010 vol. 19, num. 2, pages 201226.
BibTeX
This article introduces random
generators of plane partitions. Combining a bijection of Pak with
the framework of Boltzmann samplers, we obtain an approximatesize
and an exactsize sampler for plane partitions that have expected
complexity respectively O(n ln(n)^3 and O(n^4/3) (under a
realarithmetic computation model). To our knowledge, these are the
first polynomialtime samplers for plane partitions according to the
size. The same principles yield efficient samplers for (p x q)boxed
plane partitions (plane partitions with two dimensions bounded).
Short version : In GASCOM 06, September 2006, Dijon, France. 
Boltzmann Oracle for Combinatorial Systems,
C. Pivoteau, B. Salvy and M. Soria.
In Algorithms, Trees, Combinatorics and Probabilities, pages 475488. Discrete Mathematics and
Theoretical Computer Science, 2008. In Proceedings of the Fifth Colloquium on Mathematics and
Computer Science. Blaubeuren, Germany. September 2226, 2008.
(also available here)
BibTeX
Boltzmann random generation applies to welldefined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.

Average Analysis of Glushkov Automata under a BSTLike Model,
C. Nicaud, C. Pivoteau and B. Razet.
In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. (FSTTCS 2010), pages 388399. Chennai, India, December 2010.
(also available here)
BibTeX
We study the average number of transitions in Glushkov automata built from random regular expressions. This statistic highly depends on the probabilistic distribution set on the expressions. A recent work shows that, under the uniform distribution, regular expressions lead to automata with a linear number of transitions. However, uniform regular expressions are not necessarily a satisfying model. Therefore, we rather focus on an other model, inspired from random binary search trees (BST), which is widely used, in particular for testing. We establish that, in this case, the average number of transitions becomes quadratic according to the size of the regular expression.

Algorithms for Combinatorial Structures: WellFounded Systems and Newton Iterations,
C. Pivoteau, B. Salvy and M. Soria.
Journal of Combinatorial Theory, Series A, 119(8), pages 1711  1773, 2012.
(also available on arXiv)
BibTeX
We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing numerical values.
Our framework is an articulation of the constructible classes of Flajolet & Sedgewick with Joyal's species theory.
We extend the implicit species theorem to structures of size zero. A quadratic iterative Newton method is shown to solve wellfounded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasioptimal complexity. This iteration transfers to a numerical scheme that converges unconditionally to the values of the generating series inside their disk of convergence. These results provide important subroutines in random generation. Finally, the approach is extended to combinatorial differential systems.

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

