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

00:00:00 / 00:00:00

Chapters

Sampling algorithms and phase transitions

By Dana Randall

Appears in 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}$.

Information about the video

Date of recording 24/06/2019
Date of publication 26/07/2019
Institution CIRM
Licence CC BY NC ND
Language English
Director(s) Guillaume Hennenfent
Format MP4
Venue CIRM - Luminy

Citation data

DOI 10.24350/CIRM.V.19540103
Cite this video 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

Domain(s)

Bibliography

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

MSC codes

Document(s)

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

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback