Boltzmann Sampling

Carine Pivoteau University Pierre et Matie Curie 4 place Jussieu 75005 Paris France http://www-igm.univ-m
Monday, 13 Dec 2010 (all day)
A-212 (STCS Seminar Room)
Uniform random generation is a central issue in combinatorics, with applications in many fields of computer science. Classical random samplers are designed to generate combinatorial structures of a given size on the contrary, under the Boltzmann model, objects are generated with a randomly varying size, which allows for the design of particularly efficient samplers. The aim of this talk is to give an overview of Boltzmann method, from the original theoretical framework to effective random samplers and their applications, including recent developments.