Multiparametric Boltzmann sampling and applications

Speaker : Sergey Dovgal
Université Paris 13
Date: 13/03/2019
Time: 2:00 pm - 3:00 pm
Location: Paris-Rennes Room (EIT Digital)


  • I will describe the problem of multiparametric generation (which is #P-complete) and a relaxation of this problem (multiparametric Boltzmann sampling) for which we construct a fully polynomial algorithm. Our algorithm relies on the convex optimisation techniques, namely on the Exponential Conic Solver (ECOS) constructed in 2013 by Domahidi, Chu and Boyd.
  • The implementation of our algorithm is available on github. As a practical benchmark, we perform the tuning of regular grammars with over 1k tuning parameters, 19k states and 357k transitions in about 2 hours (the previously known algorithm was exponential in the number of parameters).
  • In order to give impression of the numerous applications of multiparametric sampling, I will present six different examples:
    • I. Software testing and code generation using lambda calculus;
    • II. Non-uniform sparse random graphs;
    • III. Belief propagation in tree decomposition for RNA design (Ponty, Will, Hammer);
    • IV. Bose-Einstein condensate in quantum harmonic oscillator represented by integer partitions;
    • V. Multiclass queuing networks (Buši? , Bouillard, Rovetta);
    • VI. Combinatorial Learning problems and connection with Maximum Likelihood approach.
  • The implementation of our algorithm can be found at