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. 201-211. 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 real-arithmetic 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, series-parallel 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 201-226.
    BibTeX

    This article introduces random generators of plane partitions. Combining a bijection of Pak with the framework of Boltzmann samplers, we obtain an approximate-size and an exact-size sampler for plane partitions that have expected complexity respectively O(n ln(n)^3 and O(n^4/3) (under a real-arithmetic computation model). To our knowledge, these are the first polynomial-time 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 475-488. Discrete Mathematics and Theoretical Computer Science, 2008. In Proceedings of the Fifth Colloquium on Mathematics and Computer Science. Blaubeuren, Germany. September 22-26, 2008. (also available here)
    BibTeX

    Boltzmann random generation applies to well-defined 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 BST-Like Model, C. Nicaud, C. Pivoteau and B. Razet. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. (FSTTCS 2010), pages 388-399. 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: Well-Founded 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 well-founded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasi-optimal 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 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