Sampling algorithms and phase transitions | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Chapitres

Sampling algorithms and phase transitions

De Dana Randall

Apparaît dans la collection : AofA: Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms / AofA: méthodes probabilistes, combinatoires et asymptotiques pour l analyse d algorithmes

Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large combinatorial sets. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they abruptly change from being efficient to inefficient as some parameter of the system is modified. Generating functions can offer an alternative approach to sampling and they play a role in showing when certain Markov chains are efficient or not. We will explore the interplay between Markov chains, generating functions, and phase transitions for a variety of combinatorial problems, including graded posets, Boltzmann sampling, and 3-colorings on $Z^{2}$.

Informations sur la vidéo

Date de captation 24/06/2019
Date de publication 26/07/2019
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Réalisateur(s) Guillaume Hennenfent
Format MP4
Lieu CIRM - Luminy

Données de citation

DOI 10.24350/CIRM.V.19540103
Citer cette vidéo Randall, Dana (24/06/2019). Sampling algorithms and phase transitions. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19540103
URL https://dx.doi.org/10.24350/CIRM.V.19540103

Domaine(s)

Bibliographie

LUBY, Michael, RANDALL, Dana, et SINCLAIR, Alistair. Markov chain algorithms for planar lattice structures. SIAM journal on Computing, 2001, vol. 31, no 1, p. 167-192. - https://doi.org/10.1137/S0097539799360355
BHAKTA, Prateek, COUSINS, Ben, FAHRBACH, Matthew, et al. Approximately sampling elements with fixed rank in graded posets. In : Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017. p. 1828-1838. - https://doi.org/10.1137/1.9781611974782.119
FAHRBACH, Matthew et RANDALL, Dana. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ferroelectric and Antiferroelectric Phases. arXiv preprint arXiv:1904.01495, 2019. - https://arxiv.org/abs/1904.01495

Codes MSC

Document(s)

https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Copyright Carmin.tv 2024

Donner son avis