Tata Institute of Fundamental Research

Boltzmann Sampling

Speaker: Carine Pivoteau University Pierre et Matie Curie 4 place Jussieu 75005 Paris France http://www-igm.univ-m
Date: Monday, 13 Dec 2010 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.