| Speaker : | Sergey Dovgal |
| Université Paris 13 | |
| Date: | 13/03/2019 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | Paris-Rennes Room (EIT Digital) |
Abstract
- 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 https://github.com/maciej-bendkowski/boltzmann-brain