Nicolas Rolin

Data Scientist

Nicolas Rolin

PhD Thesis

On usage of operators in combinatorics : construction, analysis and random generation (2016)

We study in combinatorics objects with a size (size in informatics setting can be the memory space used to represent an object). We call a combinatorial class a set of objects who for a given size have only a finite number of elements. We can for example look at text generated by a given grammar, with the number of characters as size, or trees with the number of nodes as size. A natural way of describing classes, the symbolic method, consists in decomposing objects in more elementary sub-objects with operators (disjoint union, cartesian product,…). Then we can translate theses decompositions to formal power series.The first batch of results in this thesis deals with the symbolic method and its usage. We present asymptotic results on models of increasing trees coming from concurrency theory, then we discuss on how to decompose some operators in elementary replications. The second batch of results deals with uniform random generation of objects in a given class. We first show how to generate increasing structures by adapting the recursive generation techniques to increasing product operators. Then we present two results on Boltzmann generation, with a quantitative comparison of two methods and with an extension allowing us to use approximatives values while retaining the uniformity of the generation.

Research Fields

  • Generating functions
  • Random sampling
  • Computer algebra
  • Analytic Combinatorics

Main publications

  • Probabilistic analysis of the (1+1)-evolutionary algorithm with Hsien Kuei Hwang, Alois Panholzer, Tsung-Hsi Tsai and Wei-Mei Chen, arXiv:1409.4955
  • Analytic samplers and the combinatorial rejection method with Jeremie Lumbroso and Olivier Bodini ,ANALCO 2015
  • Associativity for Binary Parallel Processes : a Quantitative Study with O. Bodini, A. Genitrini and F. Peschanski, CALDAM, Kanpur, India. 2015
  • Extended boxed product and application to synchronized trees with Olivier Bodini and Antoine Genitrini, GASCOM 2016