English
Sampling algorithms and phase transitions
Post-edited
Auteurs : ...
CIRM (Editeur )
60C05 - Combinatorial probability
60J20 - Applications of Markov chains and discrete-time Markov processes on general state spaces
68R05 - Combinatorics in connection with computer science
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf
CIRM (Editeur )
Loading the player...
|
| monotonic surfaces Markov chains integer partitions Boltzmann sampling the 6-vertex model slow mixing |
Résumé :
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}$.
Keywords : Markov chain; phase transition; integer partitions; 3-colorings
Codes MSC : Keywords : Markov chain; phase transition; integer partitions; 3-colorings
60C05 - Combinatorial probability
60J20 - Applications of Markov chains and discrete-time Markov processes on general state spaces
68R05 - Combinatorics in connection with computer science
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/1940/Slides/Randall-slides.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de publication : 26/07/2019 Date de captation : 24/06/2019 Sous collection : Research talks arXiv category : Computer Science ; Combinatorics ; Mathematical Physics ; Probability Domaine : Computer Science ; Combinatorics ; Probability & Statistics Format : MP4 (.mp4) - HD Durée : 01:10:29 Audience : Researchers Download : https://videos.cirm-math.fr/2019-06-24_Randall.mp4 
|
Informations sur la Rencontre
Nom de la rencontre : AofA: Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms / AofA: méthodes probabilistes, combinatoires et asymptotiques pour l analyse d algorithmesOrganisateurs de la rencontre : Bassino, Frédérique ; Martínez, Conrado ; Salvy, Bruno Dates : 24/06/2019 - 28/06/2019 Année de la rencontre : 2019 URL Congrès : https://conferences.cirm-math.fr/1940.html
Données de citation
DOI : 10.24350/CIRM.V.19540103Citer cette vidéo: (2019). Sampling algorithms and phase transitions. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19540103 URI : http://dx.doi.org/10.24350/CIRM.V.19540103 |
Voir aussi
- [Multi angle] Algorithms in high-dimensional non-convex landscapes / Auteur de la Conférence Zdeborova, Lenka.
- [Multi angle] The challenge of linear-time Boltzmann sampling / Auteur de la Conférence Sportiello, Andrea.
- [Multi angle] Metastability of the contact process on evolving scale-free networks / Auteur de la Conférence Mörters, Peter.
- [Multi angle] Computer algebra for lattice path combinatorics / Auteur de la Conférence Bostan, Alin.
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
